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.

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

  这道题还是比较简单的，在一个二维数组查找一个指定元素。可以直接遍历这个数组，不过已经排好序，可以先查找在哪一行，然后在对该行进行二分查找

      

1 public class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         boolean foundIndex = false;
 4         int index = 0;
 5         for(int i = 0; i < matrix.length - 1; i++){
 6             if(matrix[i][0] <= target && matrix[i + 1][0] > target){
 7                 foundIndex = true;
 8                 index = i;
 9                 break;
10             }
11         }//for
12         if(foundIndex){
13             return searchByBS(matrix[index], target);
14         }
15         else
16             return searchByBS(matrix[matrix.length - 1], target);
17     }
18     
19     /**
20      * 对数组进行二分查找
21      * @param num
22      * @return
23      */
24     public boolean searchByBS(int num[],int  target){
25         int low = 0;
26         int high = num.length - 1;
27         int middle;
28         while(low <= high){
29             middle = (low + high) / 2;
30             if(num[middle] == target)
31                 return true;
32             else if(num[middle] > target){
33                 high = middle - 1;
34             }else{
35                 low = middle + 1;
36             }//else if
37         }//while
38         return false;
39     }
40 }