题目描述 二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路1

数组每一行从左到右递增，可以对每一行进行二分查找。

bool Find(int target, vector<vector<int> > array) {
    int rows = array.size();
    int cols = array[0].size();
    if(rows==0 || cols==0)
        return false;
    int low,high;

    for(int i=0;i<rows;i++){
        low = 0;
        high = cols-1;

        while(low<=high){   // 不要忘记等号
            int mid = (low+high)/2;
            if(array[i][mid]==target){
                return true;
            }else if(array[i][mid]<target){
                low = mid + 1;   // 不要忘记+1
            }else{
                high = mid - 1;
            }
        }
    }
    return false;
}

解题思路2

选取数组的右上角数字与目标数字比较,如果该数字等于目标数字，则返回true; 如果该数字比目标数字大,剔除这一列（因为当前数字是这一列最小的了，因此这一列都比目标数字大）,否则剔除这一行（同理）。

 bool Find(int target, vector<vector<int> > array) {
    int rows = array.size();
    int cols = array[0].size();
    if(rows==0 || cols==0)
        return false;
    int row = 0;
    int col = cols-1;
    while(row<rows && col>=0){
            cout << row << col << endl;
        if(target==array[row][col])
            return true;
        else if(target<array[row][col])
            col--;
        else
            row++;
    }
    return false;
}