二维数组中的查找

题目链接
方法1：暴力枚举
其实就是一个一个数查看过去，如果找到了目标数字就返回true，否则返回false
设二维数组有n行，每行m个数字
时间复杂度：由于我们遍历了整个数组，所以时间复杂度是O(n * m)
空间复杂度：就是一个二维数组的大小，所以空间复杂度是O(n * m)

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        //暴力枚举即可
        for (int i = 0; i < array.size(); i ++ ) {
            for (int j = 0; j < array[i].size(); j ++ ) {
                if (array[i][j] == target) return true;//找到答案，直接返回true
            }
        }
        return false;//一直都没找到答案，所以返回false
    }
};

方法2：二分查找
这个方法就是在之前暴力查找的基础上加上一个二分查找的操作，对于每行进行二分查找，下面是二分查找的讲解
二分查找的前提：原数组必须有序
而我们看原题，每一行，每一列都是有序的，所以我们可以进行二分查找
对于一个数组1、4、6、19、19、19、25，31这8个数来说，加入我们要查找20是否在原数组中，过程是这样的

//a[8] = {1, 4, 6, 19, 19, 19, 25, 31};
//target = 20
int l = 0, r = 7;
while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (a[mid] <= target) l = mid;
    else r = mid - 1;
}
if (a[l] == target) return true;//l即为要找的数字下标
else return false;

我们的目的是找到小于等于target的最大值的下标
现在来模拟并且讲解一下，首先是这样的

然后我们发现，是可能的答案，而我们要找的是最大值，所以我们要继续向右区间查找，于是要，然后

发现，是错误的答案，所以我们要继续向左区间查找，于是要，然后

这里发现，是可能的答案，所以我们要继续向右区间查找，于是要，然后

这里是二分边界了，我们最后验证得到的，故不存在target这个数字。
该题的二分可以用C++ STL中的lower_bound，也可以手写二分，这里用手写二分
时间复杂度：由于我们遍历了每一行，对于每一行都是用二分查找，而二分的复杂度是O(logm)，所以时间复杂度是O(nlogm)
空间复杂度：就是一个二维数组的空间，所以是O(n * m)

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        for (int i = 0; i < array.size(); i ++ ) {
            int l = 0, r = array[i].size() - 1;
            while (l < r) {//当l == r时二分结束
                int mid = (l + r + 1) >> 1;
                //由于我们要查找的是右端点(即大于等于一个值的最大值)，所以我们要向上取整
                if (array[i][mid] <= target) l = mid;//由于该值可能是答案，所以我们用等于
                else r = mid - 1;//由于该值不可能是答案，所以我们要减一
            }
            if (!array[i].empty() && array[i][l] == target) return true;
            //注意这里要特判，由于可能出现空序列的情况，所以要加一个判断该数组是否为空
        }
        return false;
    }
};