74. Search a 2D Matrix

problem 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.

Example 1:

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

Example 2:

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

algorithm thought

第一次做这个题目的时候，我首先在行上做二分查找，然后再找到的列上在来一次二分查找。这样时间复杂度是O(lgn)，也不是很慢。但是其实这个题目就是需要一种二维的二分查找。二分查找的核心是，通过一次比较，能排除一部分数字。

这题思路是，从左上角或者右下角开始。可以思考一下，为什么从这里出发。然后一步步和target比较，并且逼近target

code

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].size()==0)
            return false;
        int i=matrix.size()-1;
        int j=0;
        while(i>=0&&j<matrix[0].size()){
            if(matrix[i][j]>target)
                i--;
            else if(matrix[i][j]<target)
                j++;
            else
                return true;
        }
        return false;
    }
};

algorithm analysis

这里时间复杂度不一定比两个二分查找更快，二分查找时间复杂度是O(lgn+lgm),这里时间复杂度最坏情况应该是O(m+n)；