74.搜索二维矩阵 (Medium)*

题目描述*

标签*

二分查找；

思路 & 代码*

这里保证了行首的元素大于上一行尾，所以可以先以行首元素二分，再在行内二分，时间复杂度 $O(\log mn)$ 。或者直接把二维转换成一维。

二分

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0) {
            return false;
        }
        int m = matrix.size(), n = matrix[0].size();
        int l = 0, r = m - 1;
        int res = -1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(matrix[mid][n - 1] >= target) {
                res = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        if(res == -1) {
            return false;
        }
        l = 0, r = n - 1;
        while(l <= r) {
            int mid = l + (r - l) / 2;
            if(matrix[res][mid] == target) {
                return true;
            }else if(matrix[res][mid] < target) {
                l = mid + 1;
            }else {
                r = mid - 1;
            }
        }
        return false;
    }
};

最后更新: July 23, 2022