074.Search a 2D Matrix

Posted on | In

Solution 1: accepted 1ms

Time: O(log(m*n)) = O(logm + logn)
Space: O(1) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix.length < 1 || matrix[0].length < 1) 
      return false;
  int m = matrix.length;
  int n = matrix[0].length;
  int lo = 0;
  int hi = m * n - 1;
  while (lo + 1 < hi) {
    int mid = lo + (hi - lo) / 2;
    int row = mid / n;
    int col = mid % n;
    if (matrix[row][col] > target)
      hi = mid;
    else if (matrix[row][col] < target)
      lo = mid;
    else
      return true;
  }
  if (matrix[lo/n][lo%n] == target || matrix[hi/n][hi%n] == target)
    return true;
  else
    return false;
}

Solution 2: accepted 0ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean searchMatrix(int[][] matrix, int target) {
  if (matrix.length < 1 || matrix[0].length < 1) 
      return false;
  int m = matrix.length;
  int n = matrix[0].length;
  int lo = 0;
  int hi = m * n - 1;
  while (lo <= hi) {  // optimized binary structure
    int mid = lo + (hi - lo) / 2;
    int value = matrix[mid / n][mid % n];  // where the improvements from 
    if (value > target)
      hi = mid - 1;
    else if (value < target)
      lo = mid + 1;
    else
      return true;
  }
  return false;
}