leetcode------Search a 2D Matrix

标题：	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]<target){
21                 start=mid+1;
22             }else{
23                 end=mid-1;
24             }
25         }
26  
27         return false;
28     }
29 }

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<n){
13             if(matrix[i][j]==target)return true;
14             else j++;
15         }
16         return false;
17         
18     }
19 }

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 True
11         return False