240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() <= 0) return false;
        int i = 0, j = matrix[0].size()-1;
        while(i < matrix.size() && j >= 0){
            if(target == matrix[i][j]) return true;
            else if(target > matrix[i][j]) i++;
            else if(target < matrix[i][j]) j--;
        }
        return false;
    }
};

思路：

从矩阵的左上角出发，如果比目标值大，向左移，如果比目标值小，向下移。出界或找到则结束。

对于一列，如果比当前值小，说明不在当前列中，列减一（缩小搜索范围）。
对于一行，如果比当前值小，则往前移动一个位置。

经过不断缩小范围（以经过的点划矩形），就可以得知目标值是否存在矩阵中。