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

题解一：暴力搜索
解题思路： 逐行逐列的搜索二维数组，判断是否存在目标值。

复杂度分析：
时间复杂度：O(MN)
空间复杂度：O(1)

实现如下：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
       for(auto i : array)//c++11语法
        {
            for(auto j : i)
            {
                if(j == target) return true;//找到目标值
            }
        }
        return false;//未找到
    }
};

题解二： 利用二分搜索
解题思路： 利用数组每行每列都是递增特性。
主要思路： 逐行使用二分搜索，查找是否含有target
如样例：分别每行使用一次二分搜索（M次二分查找）

复杂度分析：
时间复杂度：O(Mlog N )
空间复杂度：O(1)

实现如下：

class Solution {
public:
    bool binary_search(vector<int> arr,int target){//二分查找函数
        int left = 0,right = arr.size()-1;
               while(left<=right)
                {
                    int mid = (left+right)/2;
                    if(arr[mid] == target) return true;//找到了
                    else if(arr[mid] < target) left = mid+1;//往右边遍历
                    else right = mid-1;//往左边遍历
                }
                return false;
        }
    bool Find(int target, vector<vector<int> > array) {
        for(auto i : array)//c++11语法，逐行遍历；
        {
            if(binary_search(i,target)) return true;//在本行二分找到了目标值
        }
        return false;
   }

};

题解三： 线性搜索
解题思路：利用二维数组行列递增特性
主要思路：

1. 由于行列递增，可以得出：
   a.在一列中的某个数字，其上的数字都比它小
   b.在一行中的某个数字，其右的数字都比它大
2. 搜索流程：
   a.首先从数组左下角搜索.
   b.如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。
   c.查找到target,返回true; 如果越界，返回false;

示例如下：

复杂度分析:
时间复杂度:O(M+N)
空间复杂度:O(1)

实现如下:

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0)  return false;
        int r = array.size(); //行
        int l = array[0].size(); //列
        int left = 0, down = r - 1;
        while(left<l && down>=0)
        {
            int tmp = array[down][left];
            if( tmp == target) return true;
            else if(tmp < target) left++;
            else down--;
        }
        return false;
    }
};

题解四：双二分查找
解题思路： 利用数组行列递增特性。
主要思路：一维的二分查找可以舍弃一半的查找范围，二维的二分可以舍弃左上部分或者右下部分1/4的查找范围。

示例:

复杂度分析：
时间复杂度:O(logM*logN)
空间复杂度:O(1)

实现如下:

class Solution {
public:
    bool double_binary(vector<vector<int>> arr,int x1,int x2,int y1, int y2,int target){
        if(x1 == x2 || y1 == y2) return false;
        int xmid = (x1+x2)/2, ymid = (y1+y2)/2;
        int num = arr[xmid][ymid];
        if(num == target) return true;
        if(num > target)
        {
           if(double_binary(arr, x1, xmid, y1, y2, target)) return true;
           if(double_binary(arr,xmid,x2,y1,ymid,target)) return true;
        }
        else
        {
            if(double_binary(arr, xmid+1, x2, y1, y2, target)) return true;
            if(double_binary(arr, x1, xmid+1, ymid+1, y2, target)) return true;
        }
        return false;
    }
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0) return false;
        return double_binary(array, 0, array.size(), 0, array[0].size(), target);
    }
};