Search a 2D Matrix

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.

• Time: O(n)
• Space: O(1)

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int lo = 0, hi = m * n - 1;
    while (lo <= hi) {
        int mid = (hi + lo) / 2;
        if (matrix[mid / n][mid % n] == target) {
            return true;
        } else if (matrix[mid / n][mid % n] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return false;
}