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         // Start typing your Java solution below 4         // DO NOT write main() function 5         if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; 6         int i = 0; 7         for(; i < matrix.length; i ++){ 8             if(target < matrix[i][0]) { 9                 if(i < 1) return false;10                 for(int j = 0; j < matrix[i-1].length; j ++){11                     if(target == matrix[i-1][j]) return true;12                 }13                 return false;14             }15             else if(target == matrix[i][0]) return true;16         }17         for(int j = 0; j < matrix[i-1].length; j ++){18             if(target == matrix[i-1][j]) return true;19         }20         return false;21     }22 }

 第二遍：使用两次二分来加速。 一次是找到不大于target的col= 0的最值， 第二遍遍历这一row 然后找target。 如果找不到 就return false。

1 public class Solution { 2     public boolean searchMatrix(int[][] matrix, int target) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; 6         int start = 0, end = matrix.length - 1, mid = 0; 7         int i = 0, j = 0; 8         while(start <= end){ 9             mid = (start + end) / 2;10             int tmp = matrix[mid][0];11             if(tmp < target){12                 i = mid;13                 start = mid + 1;14             }else if(tmp == target) return true;15             else{16                 end = mid - 1;17             }18         }19         start = 0;20         end = matrix[0].length - 1;21         while(start <= end){22             mid = (start + end) / 2;23             int tmp = matrix[i][mid];24             if(tmp < target){25                 j = mid;26                 start = mid + 1;27             }else if(tmp == target) return true;28             else{29                 end = mid - 1;30             } 31         }32         return false;33     }34 }

 Step的方法：

1 public class Solution { 2     public boolean searchMatrix(int[][] matrix, int target) { 3         // Start typing your Java solution below 4         // DO NOT write main() function 5         if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false; 6         int row = matrix.length - 1, col = 0; 7         while(row > -1 && col < matrix[0].length){ 8             if(matrix[row][col] > target) row --; 9             else if(matrix[row][col] < target) col ++;10             else return true;11         }12         return false;13     }14 }