数组-二维数组中的查找

image.png

首先题目中描述了这个二维数组的特征，同行递增，同列递增。
第一种：
用双重循环做的，本来以为会超时，结果过了。。。
第二种：下面是书里的思路，每次检查数组的右上角。如果右上角就是要找的数字，返回True；如果右上角小于target，则可以删除本行，如果右上角大于target，则可以删除本列。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array)
        columns = len(array[0])
        row = 0
        column = columns-1
        while row <= rows-1 and column >= 0:
            if array[row][column] == target:
                return True
            elif array[row][column] > target:
                column -= 1
            else:
                row += 1
        return False

C++解法：
思路：
查找肯定是要每次比较之后，缩小寻找的区域，要选择一个数字，来和目标值比较。那么这么目标值选择的要让问题简化，这道题的解题之处就是 ，选择 右上角来作为比较的基准。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int rows = array.size();
        int cols = array[0].size();
        return helper(array, 0, cols - 1, target);
    }
private:
    bool helper(vector<vector<int>> array, int x, int y, int target){
        if(x >= array.size() || y < 0) return false;
        if(array[x][y] == target){
            return true;
        }
        if(array[x][y] < target){
            x += 1;
        }else if(array[x][y] > target){
            y -= 1;
        }
        return helper(array, x, y, target);
    }
};