题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
Solutions
1. 二分查找的方式
最直接的方法就是遍历每一行，每一行作为一个二分查找的子问题来求解：
# -*- coding:utf-8 -*-
class Solution:
def binary_tree_margins(self, array, l, r, target):
if l == r:
return False
mid_idx = int((l + r) / 2)
if array[mid_idx] == target:
return True
elif array[mid_idx] > target:
return self.binary_tree_margins(array, l, mid_idx - 1, target)
else:
return self.binary_tree_margins(array, mid_idx + 1, r, target)
def binary_tree_no_margins(self, array, target):
if len(array) == 0:
return False
mid_idx = len(array) / 2
if array[mid_idx] == target:
return True
elif array[mid_idx] > target:
return self.binary_tree_no_margins(array[:mid_idx], target)
else:
return self.binary_tree_no_margins(array[mid_idx + 1:], target)
def binary_tree(self, array, l, r, n_cols):
if l == r:
return False
mid_idx = int((l + r) / 2)
row_idx = int(mid_idx / n_cols)
col_idx = mid_idx % n_cols
print mid_idx, row_idx, col_idx, array[row_idx][col_idx]
if array[row_idx][col_idx] == target:
print '='
return True
if array[row_idx][col_idx] > target:
print '>', l, mid_idx
return self.binary_tree(array, l, mid_idx - 1, n_cols)
if array[row_idx][col_idx] < target:
print '<', mid_idx, r
return self.binary_tree(array, mid_idx + 1, r, n_cols)
# array 二维列表
def Find(self, target, array):
n_rows = len(array)
n_cols = len(array[0])
res_bool = False
for r in range(n_rows):
res_bool = res_bool or self.binary_tree_no_margins(array[r][:], target)
return res_bool
if __name__ == '__main__':
s = Solution()
array = [[1,2,3,4],[5,6,7,12],[13,17,21,23],[26,28,211,215]]
target = 7
print s.Find(target, array)
# 运行时间：312ms
# 占用内存：5752k
虽然这个办法能够解决，但是效率比较低，$O(n\log n)$ 没有利用到每一列其实也是有序的。
2. 优化解法
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
n_rows = len(array)
n_cols = len(array[0])
j = n_cols - 1
i = 0
while j >= 0 and i < n_rows:
if array[i][j] == target:
return True
elif array[i][j] > target:
j -= 1
else:
i += 1
return False
# 运行时间：221ms
# 占用内存：5624k