SearchA2dMatrix.java

// Link: https://leetcode.com/problems/search-a-2d-matrix/
// Difficulty: Medium

/*
 * Binary search
 * 0ms, 100%
 */
class Solution {
  public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length;
    int n = matrix[0].length;
    int left = 0;
    int right = m * n - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      int row = mid / n;
      int col = mid % n;
      if (matrix[row][col] == target) {
        return true;
      } else if (matrix[row][col] > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return false;
  }
}

/*
 * Time complexity: O(log(m*n))
 *
 * Space complexity: O(1)
 *
 * NOTES:
 *
 */