240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

1.每行的元素从左到右升序排列。 2. 每列的元素从上到下升序排列。 示例: 现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。 给定 target = 20，返回 false。

题目思路： 1.排除法：由于给出的矩阵是有序的，从上到下，从左到右依次递增，如果从左上角开始查找元素，发生横着数值增大，竖着走数值也会增大，所以target 在这个## 标题两个方向都会存在。但是，我们要是从右上角和左下角开始走，逐渐缩小范围，就能找到目标元素。

比如从右上角开始走，两种情况： 1.如果当前元素比 target 大，那么当前列的元素都比 target 大，’指针‘就向左移位一个（横坐标 -1 ）; 2.如果当前元素比 target 小，那么当前行元素都比 target 小，'指针’下移一位（纵坐标 +1 ）。

tip:在编码的过程中要注意数组下标越界的问题。 class Solution(object): #相当于找插入位置 def searchMatrix1(self, matrix, target): rows = len(matrix) if rows == 0: return False cols = len(matrix[0]) if cols == 0 : return False # 起点：右上角 x = 0 y = cols - 1 # 不越界的条件： 行小于等于 row -1 ，列大于等于 0 while x <=row -1 and y >=0: val = matrix[x][y] if val == target: return True elif val > target: y -=1 else : x+=1 return False

解法二：根据行列的元素有序，二分法优化搜索 过程：在对角线上迭代，二分搜索行和列，直到对角线的迭代元素用完为止。

class Solution(object): def binary_search(self,matrix,target,start,flag): left = start right = len(matrix[0]) if flag else len(matrix) while left < right: mid = left + (right - left) //2 print(left,right,mid) if flag == True: #对行进行搜索 if matrix[start][mid] == target: return True elif matrix[start][mid] < target : left = mid + 1 else: right = mid else: #对 对角线元素所在的列进行搜索 if matrix[mid][start] == target: return True elif matrix[mid][start] < target: left = mid +1 else: right = mid return False def searchMatrix(self, matrix, target): m = len(matrix) if m == 0: print('1') return False n = len(matrix[0]) if n == 0: print('2') return False for i in range(min(m,n)): row_found = self.binary_search(matrix,target,i,True) col_found = self.binary_search(matrix,target,i,False) if row_found or col_found: return True print('3') return False

Coder go go go!!!