1
class Solution {
2
  public boolean searchMatrix(int[][] matrix, int target) {
3
    int rows = matrix.length;
4
    int cols = matrix[0].length;
5
    int lo = 0, hi = rows;
6
    while (lo + 1 < hi) {
7
      int mid = lo + (hi - lo) / 2;
8
      if (matrix[mid][0] <= target) {
9
        lo = mid;
10
      } else {
11
        hi = mid;
12
      }
13
    }
14
    int[] prospect;
15
    for (int i = 0; i <= lo; i++) {
16
      prospect = matrix[i];
17
      int l = 0;
18
      int h = cols;
19
      while (l + 1 < h) {
20
        int mid = l + (h - l) / 2;
21
        if (prospect[mid] <= target) {
22
          l = mid;
23
        } else {
24
          h = mid;
25
        }
26
      }
27
      if (prospect[l] == target) {
28
        return true;
29
      }
30
    }
31
    return false;
32
  }
33
}