Course4all
Join us on telegram
Home/dsa/Binary Search/Search a 2D Matrix

Search a 2D Matrix

Master this topic with zero to advance depth.

Search a 2D Matrix

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. The matrix has the following properties: Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row.

Medium

Examples

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false
Approach 1

Level I: Brute Force

Intuition

Iterate through every row and every column to find the target. This does not take advantage of any sorting.

⏱ $O(M \\times N)$💾 $O(1)$

Detailed Dry Run

Searching for 3 in [[1,3,5...], ...]

  • [0][0]: 1
  • [0][1]: 3. Found!
java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            for (int val : row) {
                if (val == target) return true;
            }
        }
        return false;
    }
}
Approach 2

Level II: Row-wise Binary Search

Intuition

First, binary search through the first column to find which row could potentially contain the target. Then, perform a binary search within that specific row.

⏱ $O(\\log M + \\log N)$💾 $O(1)$

Detailed Dry Run

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

  1. Search first column [1, 10, 23] for row where target could be. Matrix[0][0] <= 3 < Matrix[1][0] (10). Row index 0.
  2. Binary search Row 0 [1,3,5,7] for 3. Found at index 1.
java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int up = 0, down = m - 1;
        while (up <= down) {
            int mid = up + (down - up) / 2;
            if (matrix[mid][0] <= target && target <= matrix[mid][n - 1]) {
                return binarySearch(matrix[mid], target);
            } else if (matrix[mid][0] > target) down = mid - 1;
            else up = mid + 1;
        }
        return false;
    }
    private boolean binarySearch(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == target) return true;
            if (arr[mid] < target) l = mid + 1; else r = mid - 1;
        }
        return false;
    }
}
Approach 3

Level III: Optimal (Flattened Binary Search)

Intuition

Treat the entire mtimesnm \\times n matrix as a single sorted array of size mtimesnm \\times n. We can map a 1D index idx to 2D coordinates using row = idx / n and col = idx % n.

⏱ $O(\\log(M \\times N))$💾 $O(1)$

Detailed Dry Run

StepLRMidRow=Mid/4Col=Mid%4ValDecision
10115111111 > 3 → R = 4
20420255 > 3 → R = 1
30100011 < 3 → L = 1
4111013Found!
java
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m * n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int row = mid / n, col = mid % n;
            if (matrix[row][col] == target) return true;
            if (matrix[row][col] < target) l = mid + 1; else r = mid - 1;
        }
        return false;
    }
}
← Previous QuestionSearch in Rotated Sorted Array
Next Question →Single Element in a Sorted Array