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

复杂度分析:
时间复杂度: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);
    }
};

此题同JZ1