Java Solution ...Finding the Row via binary search where target may exist


  • 0
    A

    here i am finding the row where the target may exist via binary search and then after getting the row, again applying binary search in it . Time Complexity , i suppose is O(logm +logn) (Pls correct me if I am wrong) ...

    
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            
    
               if (matrix == null || matrix.length == 0 || matrix[0].length == 0) 
                    return false;
    
            int i=0,j=matrix.length-1;  
            
            while(i<j)
            {
                int mid=i+(j-i)/2;
                if(matrix[mid][matrix[0].length-1]==target)
                    return true;
                else if(matrix[mid][matrix[0].length-1]<target)
                    i=mid+1;
                else 
                    j=mid-1;
            }
            while(target>matrix[i][matrix[0].length-1])
            {
                i++;
                if(i<0 || i>=matrix.length)
                    return false;
            }
            
            int p=0;j=matrix[0].length-1;
            while(p<=j)
            {
                int mid=(p+j)/2;
                if(matrix[i][mid]==target)
                    return true;
                else if(matrix[i][mid]<target)
                    p=mid+1;
                else
                    j=mid-1;
            }
            
            return false;
        }
    }
    

  • 0
    P

    FYI, O(logm+logn) is just the same as O(logmn). What's more u can combine ur two binary search into one. Example is as follows.

    #define ma(a, i, j, n) (n ? a[j][i] : a[i][j])
    ...
    row = 0;
    for (int c = 0; c < 2; ++c) {
        l = 0;
        r = c ? matrix[0].size()-1 : matrix.size()-1;
        while (l <= r) {
            m = l+(r-l)/2;
            t = ma(matrix, m, row, c);
            if (target < t) {
                r = m-1;
            } else if (target > t) {
                l = m+1;
            } else {
                return true;
            }
        }
        if (r < 0) {
            return false;
        }
        row = r;
    }
    return false;
    ...
    

Log in to reply
 

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