4. 二维数组中的查找

1. 想法：从第0行开始遍历，逐个扫描，如果array[i,j]>target,则抛弃后面的列。
   若小于，则行数加一，这样就可以逐渐缩小搜索范围。

class Solution:
 # array 二维列表
 def Find(self, target, array):
     # write code here
     if not array:return False
     n = len(array)
     m = len(array[0])
     for i in range(n):
         j = 0
         while j < m :
             if array[i][j] == target:
                 return True
             elif array[i][j] < target:
                 j += 1
             else:
                 m = j
     return False

2. 书上的解法：从左下角或者右上角扫描。例如左下角，大于target则i-1,小于则j+1

class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if not array:return False
        n = len(array)
        m = len(array[0])
        i = n - 1
        j = 0
        while i >= 0 and j < m:
            if array[i][j] == target:
                return True
            elif array[i][j] < target:
                    j += 1
            else:
                    i -= 1
        return False

3. 二分法，上面的时间复杂度是O（m+n），从左下角数字开始找直到找到右上角的过程，最坏情况就是m+n.而二分法的时间复杂度是O（log（mn））
   https://leetcode-cn.com/problems/search-a-2d-matrix/