74. Search a 2D Matrix

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.

本题最笨的方法就是遍历所有的元素，代码如下：

 1 public class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         if(matrix==null||matrix.length==0||matrix[0].length==0) return false;
 4         int row = matrix.length;
 5         int col = matrix[0].length;
 6         for(int i=0;i<row;i++){
 7             if(i<row-1&&target>=matrix[i+1][0]) continue;
 8             for(int j=0;j<col;j++){
 9                 if(target>matrix[i][j]) continue;
10                 else if(target==matrix[i][j]) return true;
11                 else return false;
12             }
13         }
14         return false;
15     }
16 }

看了答案才知道，可以用binary search，代码如下：

 1 public class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         if(matrix==null||matrix.length==0) return false;
 4         int left = 0;
 5         int m = matrix.length;
 6         int n = matrix[0].length;
 7         int right = m*n-1;
 8         while(left<=right){
 9             int mid = left+(right-left)/2;
10             if(matrix[mid/n][mid%n]==target) return true;
11             else if(matrix[mid/n][mid%n]>target) right = mid-1;
12             else left = mid+1;
13         }
14         return false;
15     }
16 }