题解 | #二维数组中的查找#

二分法

二分的灵活运用，二分的话，就是经过每次二分，可以确定下次该在哪一部分查找，从而舍去一部分查找区间，节省时间。本题考虑到二维数组是有序的，我们要选择一个位置，当和target比较好后，可以确定下一个位置。这里可以选择右上角或左下角的位置，以右上角为例，设右上角元素array[i][j]值为val，若val = target，返回true；若val > tar，因为val所在列的元素都比val大，所以j--；若val < tar，因为val所在行的元素都比val小，所以i++，左下角同理。

C++代码：

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