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 in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.
For example,

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
] Given target = 5, return true.

Given target = 20, return false.

原题链接

LeetCode

思路

这题的最初想法是用 binary search，这种方法肯定也是可行的，但是没有完全利用到这个 matrix 的两个特性。

先说说 binary search

这题说每行从右到左都是排好序的，那么我们就可以排除掉那些超出目标范围的行，然后对剩下的每行进行 binary search 就可以了。

Divide and Conqure

这题 divide and conqure 的做法非常有意思，我是看了九章的小视频学会的，但是真是非常机智，我觉得临场写的话除非很擅长这种智力题不然是很难想到的。。
方法的实现就是利用了这个 matrix 两个特性，即每行每列都是递增的。

假设我们从最左下角的点开始看，这个点就是当前列的最大值，还有当前行的最小值，那么如果这个点比 target 要大，那么我们是不是就可以把整行都给排除了？

如果这个点比 target 要小，我们可以把整个列都排除，所以我们就可以用一个 while 循环，来从左下角开始比较，直到我们目标找到或者整个 matrix 都排除完为止。

实现

divide and conqure

bool divideAndConqure(vector<vector<int>>& matrix, int target) {
    if (matrix.size() == 0 || matrix[0].size() == 0)
        return false;
    // start from the left bottom 
    int height = matrix.size(), width = matrix[0].size();
    int col = 0, row = height-1;
    while (col < width && row >= 0) {
        // if (row,col) equals to target, return
        if (matrix[row][col] == target) 
            return true;
        else if (matrix[row][col] > target) {
            // if (row, col) larger than target, we can exclude current row
            row--;
        } else {
            // if less than target, we can exclude current column
            // since everything from here up will be smaller than current element
            col++;
        }
    }
    return false;
}

多次 binary search

bool binarySearch(vector<vector<int>>& matrix, int target) {
    if (matrix.size() == 0 || matrix[0].size() == 0)
        return false;
    int height = matrix.size(), width = matrix[0].size();
    int begin = 0, end = matrix.size()-1;
    for (int i = 0; i < height; i++) {
        if (matrix[i][0] <= target && matrix[i][width-1] >= target) {
            // perform search
            begin = 0;
            end = width-1;
            while (begin <= end) {
                int mid = begin + (end-begin)/2;
                if (matrix[i][mid] == target) {
                    return true;
                } else if (matrix[i][mid] < target) {
                    begin = mid+1;
                } else {
                    end = mid-1;
                }
            }
        }
    }
    return false;
}

单次 binary search

public boolean binarySearch(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0)
        return false;
    if (matrix[0] == null || matrix[0].length == 0)  
        return false;
    int height = matrix.length, width = matrix[0].length;
    int start = 0, end = height*width-1;
    while (start+1 < end) {
        int mid = (start+end)/2;
        // translate index to row and column
        int row = mid / width, col = mid % width;
        if (matrix[row][col] == target)
            return true;
        else if (matrix[row][col] < target)
            start = mid;
        else
            end = mid;
    }
    if (matrix[start / width][start % width] == target)
        return true;
    if (matrix[end/width][end%width] == target) 
        return true;
    return false;          
}

复杂度分析

时间 n: height, m: width

binary search: O(nlogm), O(log(nm))

• 多次 binary search每次 search 是logm, 总共可能做 n 次 search
• 单次 binary search search 总共n*m个 element

Divide & Conqure O(m+n)

如果整个 matrix 都要排除，那么我们就是走完所有的 width 还有走完所有的 height，每次做 O(1)

空间 O(1)

没有使用额外空间

总结

这题一开始没想到 divide and conquere 做法，但是真是非常有意思。 还是需要多练习这种智力题，增加经验。