Search a 2D Matrix

search2DMatrix.java

/*
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.
*/
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {

        int m = matrix.length - 1;
        int n = matrix[0].length - 1;
        if (matrix[0][0] > target || matrix[m][n] < target) {
            return false;
        }
        // Search last row only
        if (matrix[m][0] <= target) {
            return horizontalBinarySearch(matrix[m], target) != null;
        }
        
        // Vertical Binary Search
        int i = 0;
        int j = m;
        boolean foundRow = false;
        while (!foundRow && i < j) {
            
            int midIndex = midpoint(i,j);
            if(matrix[midIndex][0] < target) {
                i = midIndex;
            } else if (matrix[midIndex][0] > target) {
                j = midIndex;
            }  else {
                return true;
            }
            
            if(j - i == 1) {
                foundRow = true;
            }
        }
        
        if (foundRow != true) {
            return false;
        }
        // Horizontal Binary Search
        return horizontalBinarySearch(matrix[i], target) != null;
    }
    
    private int midpoint(int a, int b) {
        return a + (b-a)/2;
    }
    
    private Integer horizontalBinarySearch(int[] row, int target) {
        int i = 0;
        int j = row.length - 1;
        while(i <= j) {
            int midIndex = midpoint(i,j);
            if (row[midIndex] == target) {
                return midIndex;
            } else if (row[midIndex] > target) {
                j = midIndex - 1;
            } else if (row[midIndex] < target) {
                i = midIndex + 1;
            } 
        }
        
        return null;
    }
}