74. Search a 2D Matrix

Question

You are given an m x n integer matrix matrix with the following two 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.

Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -10^4 <= matrix[i][j], target <= 10^4

Algorithm

This is a typical binary search question. You have a strictly sorted array and you are asked to find the target. Now the array is segmented on a matrix, so you need to figure out how to map the 1D array index into a 2D array.

So basically, say we have a index mid in 1-D array, in the question, the matrix is

• Each row is sorted in non-decreasing order.
• The first integer of each row is greater than the last integer of the previous row.

So we could simply make

i = mid / n;
j = mid % n;

Like this:

Code

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n;
        int mid, i, j;
        while (left < right) {
            mid = left + (right - left) / 2;
            i = mid / n;
            j = mid % n;
            if (target == matrix[i][j]) {
                return true;
            } else if (target > matrix[i][j]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return false;
    }
}