Description

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]

Given target = 3, return true.

Solution

Iteration, time O(m + n), space O(1)

从左下角或者右上角开始遍历。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int i = matrix.length - 1;
        int j = 0;
        
        while (i >= 0 && j < matrix[0].length) {
            if (target < matrix[i][j]) {
                --i;
            } else if (target > matrix[i][j]) {
                ++j;
            } else {
                return true;
            }
        }
        
        return false;
    }
}

Binary search, time O(logm + logn), space O(1)

注意这里需要先找到第一列中，最后一个小于等于target的位置，所以返回right。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int up = 0;
        int down = matrix.length - 1;
        
        // find the last element in the first column that's less or equal to target
        while (up <= down) {
            int mid = up + (down - up) / 2;
            
            if (matrix[mid][0] <= target) {
                up = mid + 1;
            } else {
                down = mid - 1;
            }
        }

        if (down < 0) {
            return false;
        }
        
        int row = down;
        int left = 0;
        int right = matrix[0].length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (matrix[row][mid] < target) {
                left = mid + 1;
            } else if (matrix[row][mid] > target) {
                right = mid - 1;
            } else {
                return true;
            }
        }
        
        return false;
    }
}