[LeetCode] #74 Search a 2D Matrix

1) search first column of the 2D array, get the last element that is <= target, search the row of that element to find target O(logN) + O(logM)
2) search all the elements in that 2D array 1 time O(log(M*N)) = O(logN) + O(logM) :p

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int start = 0;
        int end = matrix.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid][0] == target) {
                return true;
            } else if (matrix[mid][0] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        int row = target >= matrix[end][0] ? end : start;

        start = 0;
        end = matrix[0].length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[row][mid] == target) {
                return true;
            } else if (matrix[row][mid] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        if (target == matrix[row][start] || target == matrix[row][end]) {
            return true;
        }
        
        return false;
    }
}

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0][0] > target || matrix[matrix.length - 1][matrix[0].length - 1] < target) {
            return false;
        }
        
        int start = 0;
        int end = matrix.length * matrix[0].length - 1;
        int mid;
        while (start + 1 < end) {
            mid = start + (end - start) / 2;
            int x = mid / matrix[0].length;
            int y = mid % matrix[0].length;
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] < target) {
                start = mid;
            } else if (matrix[x][y] > target) {
                end = mid;
            }
        }
        if (matrix[end / matrix[0].length][end % matrix[0].length] == target) {
            return true;
        } 
        if (matrix[start / matrix[0].length][start % matrix[0].length] == target) {
            return true;
        } 
        return false;
    }
}