LeetCode75：矩阵查找（二分查找）

题目描述

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征： 每一行的数字都从左到右排序
每一行的第一个数字都比上一行最后一个数字大 例如： 对于下面的矩阵：
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
要搜索的目标值为3，返回true；

方法一：

思路分析：分块查找后再进行二分查找或者顺序查找

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> 
     * @param target int整型 
     * @return bool布尔型
     */
    bool searchMatrix(vector<vector<int> >& matrix, int target) {
        // write code here
        vector<vector<int>>::iterator i;
        i=matrix.begin();
        for(i=matrix.begin();i<matrix.end();i++){//分块查找
            int len=(*i).size()-1;
            if(target<=(*i)[len])//顺序查找
            {
                for(int j=0;j<=len;j++){
                    if(target==(*i)[j])
                        return true;
                }
                break;
            }
            /*
            if(target<=(*i)[len-1])//二分查找
            {
                int left=0,right=len-1,middle;//左右索引
                while(left<=right){
                    middle=(right+left)/2;
                    if(target==(*i)[middle])
                        return true;
                    if(target<(*i)[middle])
                        right=middle-1;
                    else if(target>(*i)[middle])
                        left=middle+1;
                }
                break;
            }*/
        }
        return false;
        
    }
};

方法二：

思路分析：
首先选取右上角数字，如果该数字等于要查找的数字，查找过程结束；
如果该数字大于要查找的数字，去掉此数字所在列；
如果该数字小于要查找的数字，则去掉该数字所在行。
重复上述过程直到找到要查找的数字，或者查找范围为空。

bool searchMatrix(vector<vector<int> > &matrix, int target){
    int i=0, j=matrix[0].size()-1;
    while(i<matrix.size() && j>=0){
        if(matrix[i][j]==target){
            return true;
        }
        else if(matrix[i][j]<target){
            i++; //去掉这一行
        }
        else{
            j--;  //去掉这一列
        }
    }
    return false;
}