Share my log(n)+log(m) solution java


  • 1
    5
    public boolean searchMatrix(int[][] matrix, int target) {
            int m=matrix.length, n=matrix[0].length;
            int left=0, right=m-1;
            //find the row of the target
            while(left<right){
                int mid = (left+right)/2;
                if(matrix[mid][n-1] == target) return true;
                if(matrix[mid][n-1] < target){
                    left = mid+1;
                }else{
                    right = mid;
                }
            }
            if( right==-1){
                return false;
            }
            if(matrix[left][n-1]==target || matrix[right][n-1]==target) return true;
            int pos = right;
            left = 0; right = n-1;
            //find the col of the target
            while(left<=right){
                int mid = (left+right)/2;
                if(matrix[pos][mid] == target) return true;
                if(matrix[pos][mid] < target){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            if(left==n || right==-1) return false;
            if(matrix[pos][left] == target || matrix[pos][right]==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.