Binary Search + Binary Search Java solution ~0ms


  • 0
    A
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) {
            return false;
        } else if (target < matrix[0][0] || target > matrix[matrix.length-1][matrix[0].length-1]) {
            return false;
        }
        
        // Binary search row, binary search within row
        int ilow = 0, ihigh = matrix.length-1;
        int jlow = 0, jhigh = matrix[0].length-1;
        
        int i = 0, j = 0;
        
        // Find which row: binary search
        while (ilow <= ihigh) {
            i = (ilow + ihigh) / 2;
    
            // Within row i
            if (matrix[i][0] <= target && target <= matrix[i][jhigh]) {
                break;
            } else if (target < matrix[i][0]) {
                ihigh = i-1;
            } else {
                ilow = i+1;
            }
        }
    
        // Find which cell: binary search
        while (jlow <= jhigh) {
            j = (jlow + jhigh) / 2;
    
            if (matrix[i][j] == target) {
                return true;
            } else if (target < matrix[i][j]) {
                jhigh = j-1;
            } else {
                jlow = j+1;
            }
        }
        return false;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.