python实现《剑指offer》之数组-二维数组中的查找

1.题目

二维数组中的查找

2.描述

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

3.解题思路

1.遍历查找 利用二维数组由上到下，由左到右递增的规律，每次将二维数组矩阵的中最左下角的数字与要查找的数字比较。 从左下角来看，向上数字递减，向右数字递增。因此从左下角开始查找，当要查找数字比左下角数字大时，右移，去掉该列；要查找数字比左下角数字小时，上移，去掉该行。如此遍历查找。时间复杂度是m+n。 2.二分查找 利用递归性，采用分治策略。 把每一行看成有序递增的数组，利用二分查找，通过遍历每一行得到答案。时间复杂度是mlogn。

python实现

1.遍历查找

class Solution: def BooleanFind(self, target, array): rows = len(array) cols= len(array[0]) i = rows -1 j = 0 while j<=cols -1 and i>=0: if target<array[i][j]: i -= 1 elif target>array[i][j]: j += 1 else: return True return False

2.二分查找

class Solution: def BinarySearch(self, target, array): rows = len(array) cols = len(array[0]) for i in range(rows): low = 0 high = cols - 1 while low <= high: mid = int((low+high)/2) if target > array[i][mid]: low = mid + 1 elif target < array[i][mid]: high = mid - 1 else: return True return False

注意： 1.数组索引从0开始。 2.range函数从0开始生成迭代序列。