Leet Code 74 Search a 2D Matrix

写一个高效的算法，在 m × n 的二维矩阵中搜索一个值。矩阵有以下性质：

每一行从左到右为升序。

每一行的第一个数都比上一行最后一个数大。

例如，有以下矩阵：

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

给定 target = 3，返回 true。

思路：二分法，目标值与 (m/2,n/2) 位置的值比较，如果相等则返回true，如果目标值小，则搜索矩阵中小于 (m/2,n/2) 的部分，否则搜索矩阵中大于 (m/2,n/2) 的部分。

1public class Solution {
2  public static boolean searchMatrix(int[][] matrix, int target) {
3    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
4      return false;
5    }
6    return searchMatrix(matrix, 0, 0, matrix.length - 1, matrix[0].length - 1,
7        target);
8  }
9
10  private static boolean searchMatrix(int[][] matrix, int top, int left,
11      int bottom, int right, int target) {
12    if (top == bottom && left == right) {
13      return matrix[top][left] == target;
14    }
15    int row = (top + bottom) >> 1;
16    int col = (left + right) >> 1;
17    if (matrix[row][col] < target) {
18      if (row + 1 <= bottom) {
19        if (searchMatrix(matrix, row + 1, left, bottom, col, target)) {
20          return true;
21        }
22      }
23      if (col + 1 <= right) {
24        if (searchMatrix(matrix, row, col + 1, bottom, right, target)) {
25          return true;
26        }
27      }
28      return false;
29    } else if (matrix[row][col] > target) {
30      if (col - 1 >= left) {
31        if (searchMatrix(matrix, top, left, row, col - 1, target)) {
32          return true;
33        }
34      }
35      if (row - 1 >= top) {
36        return searchMatrix(matrix, top, col, row - 1, right, target);
37      } else {
38        return false;
39      }
40    } else {
41      return true;
42    }
43  }
44
45}