题解 | #寻找牛群中的特定编号牛# 两次二分

知识点

二分

思路

先二分找到可能存在的行，之后再二分找到可能存在的位置，进行判断即可。

时间复杂度

AC Code (C++)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型vector<vector<>> 
     * @param target int整型 
     * @return bool布尔型
     */
    bool searchMatrix(vector<vector<int> >& matrix, int target) {
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (matrix[mid][0] < target) r = mid - 1;
            else l = mid;
        }
        int row = l;
        l = 0, r = m - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (matrix[row][mid] < target) r = mid - 1;
            else l = mid;
        }
        return matrix[row][l] == target;
    }
};