Simple O(logM + logN) Java solution


  • 0
    public boolean searchMatrix(int[][] matrix, int target) {
        
        if (matrix.length == 0)
            return false;
            
        // first locate the row in the matrix
        
        int low = 0,high = matrix.length-1,mid = (low+high)/2;
        
        while(low <= high){
            if (target >= matrix[mid][0]  && target <= matrix[mid][matrix[mid].length-1])
                break;
            else if ( target > matrix[mid][matrix[mid].length-1]){
                low = mid+1;
                mid = (low+high)/2;
            }
            else{
                high = mid-1;
                mid = (low+high)/2;
            }
        }
        
        int rowIndex = mid;
        
        // the locate that element in that row
        
        low = 0; high = matrix[rowIndex].length-1;mid = (low+high)/2;
        
        
        while(low <= high){
            if (target == matrix[rowIndex][mid])
                return true;
            else if (target > matrix[rowIndex][mid]){
                low = mid+1;
                mid = (low+high)/2;
            }
            else{
                high = mid-1;
                mid = (low+high)/2;
            }
        }
        
        return false;
        
    }

Log in to reply
 

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