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.

Example:

Consider the following matrix:

[ [1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 50] ] Given target = 3, return true.

Notes:

1. Two pass binary search, column first and then row

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return false;
        }

        int start = 0;
        int end = matrix.length-1;
        int lastColumn = matrix[0].length-1;
        while(start + 1 < end) {
            int middle = start + (end-start)/2;
            if (matrix[middle][lastColumn] == target) {
                return true;
            }

            if (matrix[middle][lastColumn] < target) {
                start = middle;
            } else {
                end = middle;
            }
        }

        int secondEnd;
        if (matrix[start][lastColumn] >= target) {
            secondEnd = start;
        } else if (matrix[end][lastColumn] >= target) {
            secondEnd = end;
        } else {
            return false;
        }

        return binarySearch(matrix[secondEnd], target);
    }

    private boolean binarySearch(int[] row, int target) {
        int start = 0;
        int end = row.length-1;
        while(start+1 < end) {
            int middle = start + (end-start)/2;
            if (row[middle] == target) {
                return true;
            }

            if (row[middle] < target) {
                start = middle;
            } else {
                end = middle;
            }
        }

        if (row[start] == target || row[end] == target) {
            return true;
        }

        return false;   
    }