leetcode 链接：74. 搜索二维矩阵

题目

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

示例：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

解答 & 代码

先二分查找定位到行，然后在该行中二分查找定位到列

时间复杂度 O(log rows + log cols)，空间复杂度 O(1)

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return false;

        int rows = matrix.size();
        int cols = matrix[0].size();

        // 外层循环二分查找定位到行
        int up = 0;
        int down = rows - 1;
        while(up <= down)
        {
            int midRow = up + (down - up) / 2;

            // 如果 target 在当前行的范围内
            if(matrix[midRow][0] <= target && matrix[midRow][cols - 1] >= target)
            {
                // 二分查找当前行以定位到列
                int left = 0;
                int right = cols - 1;
                while(left <= right)
                {
                    int midCol = left + (right - left) / 2;

                    if(matrix[midRow][midCol] == target)
                        return true;
                    else if(matrix[midRow][midCol] > target)
                        right = midCol - 1;
                    else
                        left = left + 1;
                }
                return false;
            }
            else if(matrix[midRow][0] > target)
                down = midRow - 1;
            else if(matrix[midRow][cols - 1] < target)
                up = midRow + 1;
        }
        return false;
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 81.87% 的用户
内存消耗：9.3 MB, 在所有 C++ 提交中击败了 24.36% 的用户