JZ4 二维数组中的查找

class Solution:
#     # array 二维列表
    def binary_search(self, target,array):
        left = 0
        right = len(array)-1
        while left <=right:
            mid = (left +right)//2
            if array[mid] == target:
                return True
            elif array[mid] >target:
                right = mid-1
            else:
                left = mid+1
        return False
    def Find(self, target, array):
        # write code here
        rows = len(array)
        flag = False
        for row in range(rows):
                flag = self.binary_search(target,array[row])
                if flag: return True
        return flag

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

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

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

示例如下：

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

实现如下:

class Solution:
#     # array 二维列表
    def Find(self, target, array):
        if len(array) == 0:
            return False
        rows = len(array)
        cols = len(array[0])
        left, down = 0, rows-1
        while left <cols and down>=0:
            tmp = array[down][left]
            if tmp == target:
                return True
            elif tmp <target:
                left +=1
            else:
                down-=1
        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);
    }
};