【牛客网】JZ4 二维数组中的查找

方法一的思路是：利用二维数组由上到下，由左到右递增的规律，那么选取右上角或者左下角的元素a[row][col]与target进行比较。若选取右上角，则当target小于元素a[row][col]时，那么target必定在元素a所在行的左边，即col- -；当target大于元素a[row][col]时，那么target必定在元素a所在列的下边，即row++：

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

方法二则是从第一行开始依次进行二分查找：

class Solution {
          
   
public:
    bool Find(int target, vector<vector<int> > array) {
          
   
        int i = 0;
        while(i < array.size()){
          
   
            int low = 0, high = array[0].size() - 1;
            while(low <= high){
          
   
                int mid = low + high >> 1;
                if(array[i][mid] == target) return true;
                else if(array[i][mid] > target) high = mid - 1;
                else low = mid + 1;
            }
            i++;
        }
        return false;
    }
};