剑指offer：二维数组中查找

要求如下：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数

示例如下：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

思路有三种，一种是暴力算法，这种要求不高，但是对程序开销要求大，即每一个数组元素都得遍历一遍，这里就不用细说了，会写双重循环就可以。

第二种是我采取的思路，利用折半查找：先确定目标指所在的数组，比如在二维数组的 array[3]里，然后再在array[3]里利用折半查找查目标值

第三种思路是参考其他伙伴的，这种思路利用了二维数组的数字规律，即题目里有一句：每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序

从矩阵左下角开始（右上角也可以，但是走的方式就不一样了），查找下一个目标，大于则向上走，小于则向右走，十分形象，而且有点像数据结构里面对有序二叉树的遍历，把整个矩阵当作有序数据结构，而不是只利用一维有序来进行查找，非常有新意，比较佩服所以记录在这里，而且我自己也更加倾向第三种算法。

折半查找python实现方法：

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     
 4     def Find(self,target,array):
 5         if len(array)==0 or len(array[0])==0:
 6             return  False 
 7         for x in array:#折半查找
 8             if x[0]<=target<=x[-1]:
 9                 lindex=0#左下标
10                 rindex=len(x)-1#右下标
11                 while lindex<=rindex:
12                     mid=(lindex+rindex)/2#数组中间位置元素
13                     if x[mid]==target:
14                         return True
15                     if x[mid]>target:
16                         rindex=mid-1
17                     else:
18                         lindex=mid+1
19         return False
20 
21

路径的方式实现方法：

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     # array 二维列表
 4     def Find(self, target, array):
 5         # write code here
 6         rows = len(array) - 1
 7         cols= len(array[0]) - 1
 8         i = rows
 9         j = 0
10         while j<=cols and i>=0:
11             if target<array[i][j]:
12                 i -= 1
13             elif target>array[i][j]:
14                 j += 1
15             else:
16                 return True
17         return False