| 标题： | Search a 2D Matrix |
| 通过率 | 31.3% |
| 难度 | 中等 |
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50]]
Given target = 3, return true.
本题思路清晰，就是再一个二维数组中找某个元素，那么立即想到了二分法，关键点，按行算，第k个元素的行数等于k/列数，列数等于k%列数。
还有一种思路就是，每一行的开头一定比上一行全部元素都大，那么从最后一行的第一个开始，每次比较每行的第一个，找到第一个比target小的元素，也就说明了target若存在一定在那一行，
1、二分法查找代码如下：
1 public class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 if(matrix==null || matrix.length==0 || matrix[0].length==0) 4 return false; 5 6 int m = matrix.length; 7 int n = matrix[0].length; 8 9 int start = 0;10 int end = m*n-1;11 12 while(start<=end){13 int mid=(start+end)/2;14 int midX=mid/n;15 int midY=mid%n;16 17 if(matrix[midX][midY]==target) 18 return true;19 20 if(matrix[midX][midY] 2、查找第一个小的数：
1 public class Solution { 2 public boolean searchMatrix(int[][] matrix, int target) { 3 int m=matrix.length; 4 int n=matrix[0].length; 5 int i=m-1; 6 int j=0; 7 while(i>=0){ 8 if(matrix[i][0]>target)i--; 9 else break;10 }11 if(i<0)return false;12 while(j 3、python代码：
1 class Solution: 2 def searchMatrix(self, matrix, target): 3 i, j = 0, len(matrix[0]) - 1 4 while i < len(matrix) and j >= 0: 5 if target < matrix[i][j]: 6 j -= 1 7 elif target > matrix[i][j]: 8 i += 1 9 else:10 return True11 return False