剑指offer-二维数组查找

观察数的规律，

1、数组在行和列的单调性，所以可以从行或者列的单项进行二分查找，复杂度为 n * log₂m

2、例如在待查数（<mark>7</mark>）的交叉轴形成的两个矩形中形成的空间均是大于或者小于待查值，从左上向右下递增。所以可以沿着短边形成的正方形的对角线进行比较，考虑从左上或者右下进行。例从左上开始，1，小于目标值，然后比较行列对应的尾部是否大于目标值，大于则在该行（列）中遍历，1<7，且5<7,而9>7，所以遍历第一列即可。这个可以在原本n * m的基础上适当的减小一部分需要遍历的内容，单最终还是n * m的复杂度。

3、还有一种就是从左下或者右上开始查询。查询当前行，若等于目标值就返回True，若大于目标值则上跳一行。重新从第一列遍历到最后一列。所以从复杂度的考虑上依旧是n * m。

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if len(array) == 0 or len(array[0]) == 0:
        	return False
        row = len(array)
        col = len(array[0])
        # 从左下角开始查找，若待查数小于当前值则上跳一行，大于当前值，则向右跳一行
        for i in range(row):
        	if target == array[row - i -1][0]:
        		return True
        	elif target < array[row - i -1][0]:
        		continue

        	for j in range(col):
        		if array[row - i - 1][j] == target:
        			return True
        		elif array[row - i - 1][j] > target:
        			break
        return False


# [[]] 这样的案例咩有考虑到。