突破二维数组解题惯性思维

链接原始思路

由于此二维数组中的数值分布存在左边小，下边大的规律。因此可以采用二分查找的思想，通过target和中间值的大小比较结果排除一半的值，进而缩小比较范围。

错误尝试——双重循环

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size()==0) return false;
        for(int i = 0;i<array.size();){
            for(int j = array[i].size()-1;j>=0;){
                if(target==array[i][j]) return true;
                else if(target<array[i][j]){
                    j--;//向左走
                    continue;
                }
                else if(target>array[i][j]){
                    i++;//向下走
                    break;
                }
            }
        }
        return false;
     }
};

我刚开始以为错误在于break关键字一经执行，内层循环的j值就会销毁，等到再进行内层循环的时候j就会从array.size()-1重新开始。总而言之，j并非一个全局变量。

但是我又尝试把i、j设置为全局变量、并把循环的初始条件删掉。如下：

int i=0,j = array[0].size()-1;
        for(;i<array.size();){
            for(;j>=0;)

但是还是不行。

调试了一下，终于发现问题所在—————内层循环退出之后并不默认外层循环也退出。 就算break内存循环退出之后外层循环也不会退出，因此会陷入一个死循环，报错超时。

清爽的while循环

双层循环的意义就在于判断i、j的取值范围。直接采用while单层循环进行判断即可。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.empty()||array[0].empty()) 
            return false;
        int n = array.size();
        int row = 0,col = n-1;
        while((row<n)&&(col>=0)){
            if(array[row][col]==target) return true;
            else if(array[row][col]>target) col--;
            else if(array[row][col]<target) row++;
        }
        return false;
    }
};