LeetCode 74: 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.

For example,
Consider the following matrix:

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

Given target = 3, return true.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        
        // Null matrix
        if (m == 0)
            return false;
            
        int n = matrix[0].length;
        
        // Adopt modified binary search
        int result = rank(matrix, target);
        
        if (result<0 || result>m*n-1)
            return false;
            
        int x = result/n;
        int y = result%n;
        
        return target == matrix[x][y];
    }
    
    private int rank(int[][] matrix, int target)
    {
        int m = matrix.length;
        int n = matrix[0].length;
        int lo = 0, hi = m*n-1;
        int mid, midX, midY;
        
        while (lo <= hi)
        {
            mid = lo + (hi-lo)/2;
            
            midX = mid/n;
            midY = mid%n;
            
            if (target < matrix[midX][midY])
                hi = mid-1;
            else if (target > matrix[midX][midY])
                lo = mid+1;
            else
                return mid;
        }
        
        return lo;
    }
}