Search element in a sorted matrix
Last Updated : 01 Aug, 2025
Given a sorted matrix mat[][] of size n × m and an integer x, determine whether x is present in the matrix.
The matrix is sorted in the following way:
- Each row is sorted in increasing order.
- The first element of each row is greater than or equal to the last element of the previous row
(i.e., mat[i][0] ≥ mat[i−1][m−1] for all 1 ≤ i < n).
Examples:
Input: x = 14, mat[][] = [[ 1, 5, 9],
[14, 20, 21],
[30, 34, 43]]
Output: true
Explanation: The value 14 is present in the second row, first column of the matrix.
Input: x = 42, mat[][] = [[ 1, 5, 9, 11],
[14, 20, 21, 26],
[30, 34, 43, 50]]
Output: false
Explanation: The value 42 does not appear in the matrix.
[Naive Approach] Comparing with all elements – O(n × m) Time and O(1) Space
The idea is to iterate through the entire matrix mat[][] and compare each element with x. If an element matches the x, we will return true. Otherwise, at the end of the traversal, we will return false.
C++ #include <iostream> #include <vector> using namespace std; bool searchMatrix(vector<vector<int>>& mat, int x) { int n = mat.size(); int m = mat[0].size(); // traverse every element in the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == x) return true; } } return false; } int main() { vector<vector<int>> mat = { {1, 5, 9}, {14, 20, 21}, {30, 34, 43} }; int x = 14; cout << (searchMatrix(mat, x) ? "true" : "false") << endl; } class GfG { public static boolean searchMatrix(int[][] mat, int x) { int n = mat.length; int m = mat[0].length; // traverse every element in the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == x) return true; } } return false; } public static void main(String[] args) { int[][] mat = { {1, 5, 9}, {14, 20, 21}, {30, 34, 43} }; int x = 14; System.out.println(searchMatrix(mat, x) ? "true" : "false"); } } def searchMatrix(mat, x): n = len(mat) m = len(mat[0]) # traverse every element in the matrix for i in range(n): for j in range(m): if mat[i][j] == x: return True return False if __name__ == "__main__": mat = [ [1, 5, 9], [14, 20, 21], [30, 34, 43] ] x = 14 print("true" if searchMatrix(mat, x) else "false") using System; class GfG { public static bool searchMatrix(int[][] mat, int x) { int n = mat.Length; int m = mat[0].Length; // traverse every element in the matrix for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (mat[i][j] == x) return true; } } return false; } public static void Main(string[] args) { int[][] mat = new int[][] { new int[] {1, 5, 9}, new int[] {14, 20, 21}, new int[] {30, 34, 43} }; int x = 14; Console.WriteLine(searchMatrix(mat, x) ? "true" : "false"); } } function searchMatrix(mat, x) { let n = mat.length; let m = mat[0].length; // traverse every element in the matrix for (let i = 0; i < n; i++) { for (let j = 0; j < m; j++) { if (mat[i][j] === x) return true; } } return false; } // Driver Code let mat = [ [1, 5, 9], [14, 20, 21], [30, 34, 43] ]; let x = 14; console.log(searchMatrix(mat, x) ? "true" : "false"); [Better Approach] Using Binary Search Twice - O(log n + log m) Time and O(1) Space
First, we locate the row where the target x might be by using binary search, and then we apply binary search again within that row. To find the correct row, we perform binary search on the first elements of the middle row.
Step By Step Implementations:
=> Start with low = 0 and high = n - 1.
=> If x is smaller than the first element of the middle row (a[mid][0]), then x will be smaller than all elements in rows >= mid, so update high = mid - 1.
=> If x is greater than the first element of the middle row (a[mid][0]), then x will be greater than all elements in rows < mid, so store the current mid row and update low = mid + 1.
Once we have found the correct row, we can apply binary search within that row to search for the target element x.
C++ #include <iostream> #include <vector> using namespace std; // function to binary search for x in arr[] bool search(vector<int> &arr, int x) { int lo = 0, hi = arr.size() - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (x == arr[mid]) return true; if (x < arr[mid]) hi = mid - 1; else lo = mid + 1; } return false; } // function to search element x in fully // sorted matrix bool searchMatrix(vector<vector<int>> &mat, int x) { int n = mat.size(), m = mat[0].size(); int lo = 0, hi = n - 1; int row = -1; while (lo <= hi) { int mid = (lo + hi) / 2; // if the first element of mid row is equal to x, // return true if (x == mat[mid][0]) return true; // if x is greater than first element of mid row, // store the mid row and search in lower half if (x > mat[mid][0]) { row = mid; lo = mid + 1; } // if x is smaller than first element of mid row, // search in upper half else hi = mid - 1; } // if x is smaller than all elements of mat[][] if (row == -1) return false; return search(mat[row], x); } int main() { vector<vector<int>> mat = {{1, 5, 9}, {14, 20, 21}, {30, 34, 43}}; int x = 14; if (searchMatrix(mat, x)) cout << "true"; else cout << "false"; return 0; } class GfG { // function to binary search for x in arr[] static boolean search(int[] arr, int x) { int lo = 0, hi = arr.length - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (x == arr[mid]) return true; if (x < arr[mid]) hi = mid - 1; else lo = mid + 1; } return false; } // function to search element x in fully // sorted matrix static boolean searchMatrix(int[][] mat, int x) { int n = mat.length, m = mat[0].length; int lo = 0, hi = n - 1; int row = -1; while (lo <= hi) { int mid = (lo + hi) / 2; // if the first element of mid row is equal to x, // return true if (x == mat[mid][0]) return true; // if x is greater than first element of mid row, // store the mid row and search in lower half if (x > mat[mid][0]) { row = mid; lo = mid + 1; } // if x is smaller than first element of mid row, // search in upper half else hi = mid - 1; } // if x is smaller than all elements of mat[][] if (row == -1) return false; return search(mat[row], x); } public static void main(String[] args) { int[][] mat = { {1, 5, 9}, {14, 20, 21}, {30, 34, 43} }; int x = 14; if (searchMatrix(mat, x)) System.out.println("true"); else System.out.println("false"); } } # function to binary search for x in arr[] def search(arr, x): lo = 0 hi = len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if x == arr[mid]: return True if x < arr[mid]: hi = mid - 1 else: lo = mid + 1 return False # function to search element x in fully # sorted matrix def searchMatrix(mat, x): n = len(mat) m = len(mat[0]) lo = 0 hi = n - 1 row = -1 while lo <= hi: mid = (lo + hi) // 2 # if the first element of mid row is equal to x, # return true if x == mat[mid][0]: return True # if x is greater than first element of mid row, # store the mid row and search in lower half if x > mat[mid][0]: row = mid lo = mid + 1 # if x is smaller than first element of mid row, # search in upper half else: hi = mid - 1 # if x is smaller than all elements of mat[][] if row == -1: return False return search(mat[row], x) if __name__ == "__main__": mat = [[1, 5, 9], [14, 20, 21], [30, 34, 43]] x = 14 if searchMatrix(mat, x): print("true") else: print("false") using System; class GfG { // function to binary search for x in arr[] static bool Search(int[] arr, int x) { int lo = 0, hi = arr.Length - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (x == arr[mid]) return true; if (x < arr[mid]) hi = mid - 1; else lo = mid + 1; } return false; } // function to search element x in fully // sorted matrix static bool SearchMatrix(int[][] mat, int x) { int n = mat.Length, m = mat[0].Length; int lo = 0, hi = n - 1; int row = -1; while (lo <= hi) { int mid = (lo + hi) / 2; // if the first element of mid row is equal to x, // return true if (x == mat[mid][0]) return true; // if x is greater than first element of mid row, // store the mid row and search in lower half if (x > mat[mid][0]) { row = mid; lo = mid + 1; } // if x is smaller than first element of mid row, // search in upper half else hi = mid - 1; } // if x is smaller than all elements of mat[][] if (row == -1) return false; return Search(mat[row], x); } static void Main(string[] args) { int[][] mat = new int[][] { new int[] {1, 5, 9}, new int[] {14, 20, 21}, new int[] {30, 34, 43} }; int x = 14; if (SearchMatrix(mat, x)) Console.WriteLine("true"); else Console.WriteLine("false"); } } // function to binary search for x in arr[] function search(arr, x) { let lo = 0, hi = arr.length - 1; while (lo <= hi) { let mid = Math.floor((lo + hi) / 2); if (x === arr[mid]) return true; if (x < arr[mid]) hi = mid - 1; else lo = mid + 1; } return false; } // function to search element x in fully // sorted matrix function searchMatrix(mat, x) { let n = mat.length, m = mat[0].length; let lo = 0, hi = n - 1; let row = -1; while (lo <= hi) { let mid = Math.floor((lo + hi) / 2); // if the first element of mid row is equal to x, // return true if (x === mat[mid][0]) return true; // if x is greater than first element of mid row, // store the mid row and search in lower half if (x > mat[mid][0]) { row = mid; lo = mid + 1; } // if x is smaller than first element of mid row, // search in upper half else hi = mid - 1; } // if x is smaller than all elements of mat[][] if (row === -1) return false; return search(mat[row], x); } // Driver code const mat = [ [1, 5, 9], [14, 20, 21], [30, 34, 43] ]; const x = 14; if (searchMatrix(mat, x)) console.log("true"); else console.log("false"); [Expected Approach] Using Binary Search Once - O(log(n × m)) and O(1) Space
The idea is to consider the given matrix as 1D array and apply only one binary search.
For example, for a matrix of size n x m and we can consider it as a 1D array of size n*m, then the first index would be 0 and last index would n*m-1. So, we need to do binary search from low = 0 to high = (n*m-1).
How to find the element in 2D matrix corresponding to index = mid?
Since each row of mat[][] will have m elements, so we can find the row of the element as (mid / m) and the column of the element as (mid % m). Then, we can compare x with arr[mid/m][mid%m] for each mid and complete our binary search.
C++ #include <iostream> #include <vector> using namespace std; bool searchMatrix(vector<vector<int>>& mat, int x) { int n = mat.size(), m = mat[0].size(); int lo = 0, hi = n * m - 1; while (lo <= hi) { int mid = (lo + hi) / 2; // find row and column of element at mid index int row = mid / m; int col = mid % m; // if x is found, return true if (mat[row][col] == x) return true; // if x is greater than mat[row][col], search // in right half if (mat[row][col] < x) lo = mid + 1; // if x is less than mat[row][col], search // in left half else hi = mid - 1; } return false; } int main() { vector<vector<int>> mat = {{1, 5, 9}, {14, 20, 21}, {30, 34, 43}}; int x = 14; if (searchMatrix(mat, x)) cout << "true"; else cout << "false"; return 0; } class GfG { static boolean searchMatrix(int[][] mat, int x) { int n = mat.length, m = mat[0].length; int lo = 0, hi = n * m - 1; while (lo <= hi) { int mid = (lo + hi) / 2; // find row and column of element at mid index int row = mid / m; int col = mid % m; // if x is found, return true if (mat[row][col] == x) return true; // if x is greater than mat[row][col], search // in right half if (mat[row][col] < x) lo = mid + 1; // if x is less than mat[row][col], search // in left half else hi = mid - 1; } return false; } public static void main(String[] args) { int[][] mat = {{1, 5, 9}, {14, 20, 21}, {30, 34, 43}}; int x = 14; if (searchMatrix(mat, x)) System.out.println("true"); else System.out.println("false"); } } def searchMatrix(mat, x): n = len(mat) m = len(mat[0]) lo, hi = 0, n * m - 1 while lo <= hi: mid = (lo + hi) // 2 # find row and column of element at mid index row = mid // m col = mid % m # if x is found, return true if mat[row][col] == x: return True # if x is greater than mat[row][col], search # in right half if mat[row][col] < x: lo = mid + 1 # if x is less than mat[row][col], search # in left half else: hi = mid - 1 return False if __name__ == "__main__": mat = [[1, 5, 9], [14, 20, 21], [30, 34, 43]] x = 14 if searchMatrix(mat, x): print("true") else: print("false") using System; class GfG { // function to search for x in the matrix // using binary search static bool searchMatrix(int[,] mat, int x) { int n = mat.GetLength(0), m = mat.GetLength(1); int lo = 0, hi = n * m - 1; while (lo <= hi) { int mid = (lo + hi) / 2; // find row and column of element at mid index int row = mid / m; int col = mid % m; // if x is found, return true if (mat[row, col] == x) return true; // if x is greater than mat[row, col], search // in right half if (mat[row, col] < x) lo = mid + 1; // if x is less than mat[row, col], search // in left half else hi = mid - 1; } return false; } static void Main() { int[,] mat = { { 1, 5, 9 }, { 14, 20, 21 }, { 30, 34, 43 } }; int x = 14; if (searchMatrix(mat, x)) Console.WriteLine("true"); else Console.WriteLine("false"); } } function searchMatrix(mat, x) { let n = mat.length, m = mat[0].length; let lo = 0, hi = n * m - 1; while (lo <= hi) { let mid = Math.floor((lo + hi) / 2); // find row and column of element at mid index let row = Math.floor(mid / m); let col = mid % m; // if x is found, return true if (mat[row][col] === x) return true; // if x is greater than mat[row][col], search // in right half if (mat[row][col] < x) lo = mid + 1; // if x is less than mat[row][col], search // in left half else hi = mid - 1; } return false; } // Driver Code let mat = [[1, 5, 9], [14, 20, 21], [30, 34, 43]]; let x = 14; if (searchMatrix(mat, x)) console.log("true"); else console.log("false");
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile