个人技术分享

leetCode74. 搜索二维矩阵

二分法模板：见到背过就行

// 区间[L,R]被划分为[L,mid]和[mid + 1, R]时使用这个模板
int bsearch_1(int l, int r){
    while(l < r){
        int mid = l + r >> 1;
        if(check(mid)) r = mid; //check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}

// 区间[L,R]被划分为[L,mid - 1]和[mid, R]时使用这个模板
int bsearch_2(int l, int r){
    while(l < r){
        int mid = l + r + 1 >> 1; // 加1进行补偿：原因是当mid = left会陷入死循环（记住即可）
        if(check(mid)) l = mid; //check()判断mid是否满足性质
        else r = mid - 1;
    }
    return l;
}

题目思路：

代码

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 力扣特殊：对空数组的特判
        if(matrix.empty() || matrix[0].empty() ) return false;

        int n = matrix.size(), m = matrix[0].size();
        int left = 0, right = n * m - 1;
        while(left < right){
            int mid = left + right >> 1;
            if(matrix[mid / m][mid % m] >= target) right = mid;
            else left = mid + 1;
        }

        return matrix[left / m][left % m] == target;
    }
};