Java O(lgm + lgn) Sol Using binary search


  • 1
    J
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) return false;
        int numRow = matrix.length;
        int numCol = matrix[0].length;
        
        //if (matrix[0][0] > target || matrix[numRow - 1][numCol - 1] < target) return false;
        
        int top = 0, left = 0, right = numCol - 1, bottom = numRow - 1;
        
        while (bottom > top) {
            int mid = (top + bottom) / 2 + (top + bottom) % 2;
            if (matrix[mid][left] == target) return true;
            else if (matrix[mid][left] > target) bottom = mid - 1;
            else top = mid;
        }
        
        while (right > left) {
            int mid = (left + right) / 2;
            if (matrix[top][mid] == target) return true;
            else if (matrix[top][mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        
        if (matrix[top][left] == target) return true;
        return false;
    }

Log in to reply
 

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