Java Array.binarySearch O(log(mn)), but use extra 1d space


  • 0
    C

    Play with array library binarySearch(), careful with the return value.
    O(log(mn))
    Easy to understand and code.

    public class Solution {

    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length==0||matrix[0].length==0||target<matrix[0][0]) return false;
        int r = matrix.length, c=matrix[0].length, help[]=new int[r], i=0;
        
        for(;i<r;i++) help[i]=matrix[i][c-1];
    
        i=Arrays.binarySearch(help,target);
        if(i>=0) return true;
        i=i<0?-i-1:i;
        if(i>r-1) return false;
        // target bigger than the last one in last row
        i=Arrays.binarySearch(matrix[i],target);
        return i>=0;
    }
    

    }


Log in to reply
 

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