[Lc]74搜索二维矩阵

题目

题解

稍微变形的二分查找，其实写法是一样的，主要就是在取mid的时候需要转化一下，开始取二分查找最初的left和right也要注意，还有二分查找要传入matrix的长宽m，n

• 时间复杂度$O(log{mn})$
• 空间复杂度$O(1)$

class Solution {//时间复杂度O(log2(mn)),标准二分查找
private:
    bool BinarySearch(vector<vector<int>>& matrix,int target, int left, int right, int m, int n){//设计递归函数，使用二分查找
        if(left>right) return false;//这一步防止无限递归，判断是否left>=right
        int mid = (left+right)/2;//计算中间值
        int midElement = matrix[mid/n][mid%n];//读取中间值的参数
        if(midElement==target) return true;//如果中间值等于目标值，则返回true
        else if(midElement>target) return BinarySearch(matrix,target,left,mid-1,m,n);
        //若目标值小于中间值，则选取前半段进行递归
        else if(midElement<target) return BinarySearch(matrix,target,mid+1,right,m,n);
        //若目标值大于中间值，则选取后半段进行递归
        return false;//若没有相等的，返回false
    }
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        int m = matrix.size();
        int n = matrix[0].size();//计算数组的长宽
        return BinarySearch(matrix,target,0,m*n-1,m,n);//调用二分查找函数

    }

};