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
2
3
4
5
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

思路

可以利用二分法进行查找。由于矩阵是按行按列顺序组织的，先寻找最后一列的数，哪一个大于并最接近目标数(target)。这个数对应的那一行就是目标数所在的那一行。再在这一行利用二分法寻找即可。总共用两次二分法，时间复杂度是O(log(m+n))。

二分法搜索成功的关键就是要在纸上理清楚思路才行。注意22行、39行low=mid+1的处理方法，不然会让结果陷入死循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length > 0){
            if(matrix[0].length > 0){
                int start = matrix[0][0];
                int end = matrix[matrix.length - 1][matrix[0].length - 1];
                if(target < start || target > end) return false;
                else{
                    int low = 0;
                    int high = matrix.length - 1;
                    int mid = 0;
                    //Binary Search for the last column of whole matrix.
                    while(low < high){
                        mid = (low + high) / 2;
                        if(matrix[mid][matrix[0].length-1] > target){
                            high = mid;
                        }
                        else if(matrix[mid][matrix[0].length-1] == target){
                            return true;
                        }
                        else{
                            low = mid + 1;
                        }
                    }
                    //The target line has found.
                    int line = low;
                    low = 0;
                    high = matrix[0].length - 1;
                    //Binary Search in the target line.
                    while(low < high){
                        mid = (low + high) / 2;
                        if(matrix[line][mid] > target){
                            high = mid;
                        }
                        else if(matrix[line][mid] == target){
                            return true;
                        }
                        else{
                            low = mid + 1;
                        }
                    }
                    if(matrix[line][low] == target) return true;
                    else return false;
                }
            }
            else return false;
        }
        else return false;
    }
}