[数据结构与算法]leetcode 240

思路一：二分搜索

1.由于矩阵行和列都是从小到大排序的，容易发现，matrix[x][y]>=matrix[i][j]，其中0<=i<x<m，0<=j<y<n；matrix[x][y]<=matrix[i][j]，其中x<i<m，y<j<n。
2.由1可知，我们可以将矩阵分成4个部分，上下左右，如果确定matrix[x][y]<target<matrix[x+1][y+1]，则可以确定target只能出现在左下角矩阵或者右上角矩阵。
3.由2我们可以总结出一种递归的解法

实现
记矩阵当前最左上角元素（x1，y1）、右下角元素（x2，y2）
1.如果x1>x2或者y1>y2，则该子矩阵不存在，故找不到target，返回false
2.记中间行mid为（y1+y2）/2，则在mid行中确定分界点（x，y），使得matrix[x-1][mid]<target，matrix[x-1][mid]>target。
3.递归搜索左下角子矩阵（x1,mid+1）（x-1,y2）和右上角子矩阵（x，y1）（x2,mid）

代码：

class Solution {
public:
    bool partSearch(vector<vector<int>>& matrix,int target,int x1,int y1,int x2,int y2)
    {
        if(x1>x2||y1>y2)
            return false;
        int mid=(y1+y2)/2;
        int i=x1;
        for(i=x1;i<=x2;i++)
        {
            if(matrix[mid][i]>target)
                break;
            else if(matrix[mid][i]==target)
                return true;
        }
        return partSearch(matrix,target,x1,mid+1,i-1,y2)||partSearch(matrix,target,i,y1,x2,mid-1);
    }
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m1=matrix.size();
        int n1=matrix[0].size();
        return partSearch(matrix,target,0,0,n1-1,m1-1);
    }
};

思路二：

1.从最左下角元素(x,y)开始搜索
2.如果当前元素等于target，则找到；如果小于target，则向上走一步，也就是y–，根据思路一的1总结出的特性，（x,y）是子矩阵(0,0) (x,y)最大元素，左边没路走，只能往上面走；如果大于target，则向右走一步，(x,y）是子矩阵(x,y) (m-1,n-1)最小元素，下面的路已经走过，只能往右边走。

代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m1=matrix.size();
        int n1=matrix[0].size();
        int x=m1-1;
        int y=0;
        while(x>=0&&x<m1&&y>=0&&y<n1)
        {
            if(matrix[x][y]>target)
            {
                x--;
            }
            else if(matrix[x][y]==target)
            {
                return true;
            }
            else
            {
                y++;
            }
        }
        return false;
    }
};