Open In App

Search in matrix where only individual columns are sorted

Last Updated : 23 Jul, 2025
Suggest changes
Share
2 Likes
Like
Report

Given an n * m semi-sorted 2D matrix, mat[][] where each column is individually sorted in ascending order but the rows are not sorted, and a target element x. The task is to find the position (row and column index) of x in the matrix. If the element is not found, return -1.

Examples: 

Input: mat[][] = [[1, 4, 7],
[2, 5, 8],
[3, 6, 9]]
x = 5
Output: (1, 1)
Explanation: Element 5 is present in the matrix at row index 1 and column index 1.


Input: mat[][] = [[10, 20, 30],
[15, 25, 35],
[18, 28, 40]]
x = 26
Output: -1
Explanation: Element 26 is not found in any column of the matrix, so the output is -1.

Table of Content

[Naive Approach] - O(n*m) Time and O(1) Space

We linearly scan each element of the matrix and compare it with the target x, moving through every row and column since there is no row-wise order.
For detailed explanation and code please refer Searching Algorithms for 2D Arrays (Matrix).

[Expected Approach] Using Binary Search - O(m*log(n)) Time and O(1) Space

The idea is to leverage the sorted property of each column in the matrix. Since each column is individually sorted, we can apply binary search column-wise to speed up the search which is more efficient than linear search.

C++ 
// C++ program to search an element in a // column-wise sorted matrix using Binary Search #include <bits/stdc++.h> using namespace std; // Function to perform binary search in a column int binarySearchColumn(vector<vector<int>> &mat,  int col, int x) {  int low = 0;  int high = mat.size() - 1;  while (low <= high) {  int mid = (low + high) / 2;  // Check if mid element is the target  if (mat[mid][col] == x) {  return mid;  }  // If mid element is less than x, move down  else if (mat[mid][col] < x) {  low = mid + 1;  }  // Else move up  else {  high = mid - 1;  }  }  // Element not found in this column  return -1; } // Function to search x in column-wise sorted matrix vector<int> searchInSemiSortedMatrix(  vector<vector<int>> &mat, int x) {  int rows = mat.size();  int cols = mat[0].size();  // Apply binary search on each column  for (int col = 0; col < cols; col++) {  int row = binarySearchColumn(mat, col, x);  if (row != -1) {  return {row, col};  }  }  // Element not found in any column  return {-1}; } // Driver code int main() {  vector<vector<int>> mat = {  {1, 4, 7},  {2, 5, 8},  {3, 6, 9}  };  int x = 5;  vector<int> pos = searchInSemiSortedMatrix(mat, x);  if (pos.size() == 2) {  cout << "(" << pos[0] << ", "   << pos[1] << ")";  }   else {  cout << "-1";  }  return 0; }
Java 
// Java program to search an element in a // column-wise sorted matrix using Binary Search class GfG {  // Function to perform binary search in a column  static int binarySearchColumn(int[][] mat,  int col, int x) {  int low = 0;  int high = mat.length - 1;  while (low <= high) {  int mid = (low + high) / 2;  // Check if mid element is the target  if (mat[mid][col] == x) {  return mid;  }  // If mid element is less than x, move down  else if (mat[mid][col] < x) {  low = mid + 1;  }  // Else move up  else {  high = mid - 1;  }  }  // Element not found in this column  return -1;  }  // Function to search x in column-wise sorted matrix  static int[] searchInSemiSortedMatrix(int[][] mat, int x) {  int rows = mat.length;  int cols = mat[0].length;  // Apply binary search on each column  for (int col = 0; col < cols; col++) {  int row = binarySearchColumn(mat, col, x);  if (row != -1) {  return new int[]{row, col};  }  }  // Element not found in any column  return new int[]{-1};  }  // Driver code  public static void main(String[] args) {  int[][] mat = {  {1, 4, 7},  {2, 5, 8},  {3, 6, 9}  };  int x = 5;  int[] pos = searchInSemiSortedMatrix(mat, x);  if (pos.length == 2) {  System.out.print("(" + pos[0] + ", " + pos[1] + ")");  } else {  System.out.print("-1");  }  } }
Python 
# Python program to search an element in a # column-wise sorted matrix using Binary Search # Function to perform binary search in a column def binarySearchColumn(mat, col, x): low = 0 high = len(mat) - 1 while low <= high: mid = (low + high) // 2 # Check if mid element is the target if mat[mid][col] == x: return mid # If mid element is less than x, move down elif mat[mid][col] < x: low = mid + 1 # Else move up else: high = mid - 1 # Element not found in this column return -1 # Function to search x in column-wise sorted matrix def searchInSemiSortedMatrix(mat, x): rows = len(mat) cols = len(mat[0]) # Apply binary search on each column for col in range(cols): row = binarySearchColumn(mat, col, x) if row != -1: return [row, col] # Element not found in any column return [-1] # Driver code if __name__ == '__main__': mat = [ [1, 4, 7], [2, 5, 8], [3, 6, 9] ] x = 5 pos = searchInSemiSortedMatrix(mat, x) if len(pos) == 2: print(f"({pos[0]}, {pos[1]})") else: print("-1")
C# 
// C# program to search an element in a // column-wise sorted matrix using Binary Search using System; class GfG {  // Function to perform binary search in a column  static int binarySearchColumn(int[,] mat,  int col, int x) {  int low = 0;  int high = mat.GetLength(0) - 1;  while (low <= high) {  int mid = (low + high) / 2;  // Check if mid element is the target  if (mat[mid, col] == x) {  return mid;  }  // If mid element is less than x, move down  else if (mat[mid, col] < x) {  low = mid + 1;  }  // Else move up  else {  high = mid - 1;  }  }  // Element not found in this column  return -1;  }  // Function to search x in column-wise sorted matrix  static int[] searchInSemiSortedMatrix(int[,] mat, int x) {  int rows = mat.GetLength(0);  int cols = mat.GetLength(1);  // Apply binary search on each column  for (int col = 0; col < cols; col++) {  int row = binarySearchColumn(mat, col, x);  if (row != -1) {  return new int[]{row, col};  }  }  // Element not found in any column  return new int[]{-1};  }  // Driver code  static void Main() {  int[,] mat = {  {1, 4, 7},  {2, 5, 8},  {3, 6, 9}  };  int x = 5;  int[] pos = searchInSemiSortedMatrix(mat, x);  if (pos.Length == 2) {  Console.Write("(" + pos[0] + ", " + pos[1] + ")");  } else {  Console.Write("-1");  }  } }
JavaScript 
// JavaScript program to search an element in a // column-wise sorted matrix using Binary Search // Function to perform binary search in a column function binarySearchColumn(mat, col, x) {  let low = 0;  let high = mat.length - 1;  while (low <= high) {  let mid = Math.floor((low + high) / 2);  // Check if mid element is the target  if (mat[mid][col] === x) {  return mid;  }  // If mid element is less than x, move down  else if (mat[mid][col] < x) {  low = mid + 1;  }  // Else move up  else {  high = mid - 1;  }  }  // Element not found in this column  return -1; } // Function to search x in column-wise sorted matrix function searchInSemiSortedMatrix(mat, x) {  let rows = mat.length;  let cols = mat[0].length;  // Apply binary search on each column  for (let col = 0; col < cols; col++) {  let row = binarySearchColumn(mat, col, x);  if (row !== -1) {  return [row, col];  }  }  // Element not found in any column  return [-1]; } // Driver code let mat = [  [1, 4, 7],  [2, 5, 8],  [3, 6, 9] ]; let x = 5; let pos = searchInSemiSortedMatrix(mat, x); if (pos.length === 2) {  console.log(`(${pos[0]}, ${pos[1]})`); } else {  console.log("-1"); }

Output
(1, 1)

K
kartik
Article Tags :

Explore

Lightbox