二分查找：74搜索二维矩阵

74：搜索二维矩阵

思路：根据二维矩阵的定义是从左到右依次递增且这一行的第一个数大于前一行的最后一个数的思路我们可以先确定行的位置，再确定列的位置。

方法1：将二维矩阵按照行转化为一维的。

思路：首先确定循环不变量的设置，判断行的时候使用的是[up,down)的左开右闭的方式，判断列的时候使用的是[left,right]的方式。

具体实现：

1.判断在mid行：target大于等于mid行对应的最左边的位置，小于等于mid行对应的最右边的位置，结束循环。

2.判断在mid下面即[mid+1,down)，此时需要比较的是大于mid行的最右侧的位置。

3.判断在mid上面即[up,mid),此时需要比较的就是小于mid行最左侧的位置。

4.边界判断：当target大于matrix的最大值或者最小值的时候，此时up为-1或者down = matrix.size()会超出边界，所以在前面结束之后需要加上一个边界判断。

5.对这一列的判断可以参考二分查找的方式（可以看二分查找），最后来确定是否存在。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {      
        int up=0;int down=matrix.size();
        int left=0,right=matrix[0].size()-1;
        while(up<down){
            int mid=up+(down-up)/2;
            if(target>=matrix[mid][0]&&target<=matrix[mid][right]){
                up = mid;down = mid;break;
            }
            if(target<matrix[mid][0])down=mid;
            if(target>matrix[mid][right])up=mid+1;
        }
        if(up>matrix.size()-1)return false;//边界判断是否超限
        if(down<0)return false;
        cout<<up<<endl;
        while(left<=right){//这个地方改成等于号【left，right】
            int mid=left+(right-left+1)/2;
            cout<<left<<" "<<right<<" "<<mid<<" "<<matrix[up][mid]<<endl;
            if(target<matrix[up][mid])right=mid-1;//这个地方应该是要-1
            else if(target>matrix[up][mid])left=mid+1;
            else return true;
        }
        
        
    return false;
    }
};

方法2：将其展开成一个一维的数组，再进行查找

思路：由于展开之后是递增的，所以可以使用二分查找的思路来进行一个查找。

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