Search a 2D Matrix (Flat Binary Search)

Share

Given sorted m x n matrix (each row starts after last of previous), search for a target using O(log(M*N)) binary search.

Example 1
Input: [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3 → Output: true

Solution Approach

Treat as flat array: row = mid/n, col = mid%n.

  • lo=0, hi=m*n-1.
  • mid=lo+(hi-lo)/2; val=matrix[mid/n][mid%n].
  • Compare to target; adjust lo/hi.
Java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length, n=matrix[0].length, lo=0, hi=m*n-1;
        while (lo<=hi){
            int mid=lo+(hi-lo)/2, val=matrix[mid/n][mid%n];
            if (val==target) return true;
            else if (val<target) lo=mid+1; else hi=mid-1;
        }
        return false;
    }
}
  • Time Complexity: O(log(M*N))
  • Space Complexity: O(1)