Java Double Binary Search (what is the time complexity?)


  • 0
    X

    I'm not sure the exact time complexity of this code. The basic idea is just to use standard binary on both sides of row and column to minimize the searching area until it reaches the final one element.

    public class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix==null || matrix.length==0 || matrix[0].length==0) return false;
            int m=matrix.length;
            int n=matrix[0].length;
            return search2D(matrix, 0, m-1, 0, n-1, target);        
        }
        
        private boolean search2D (int[][] matrix, int mS, int mE, int nS, int nE, int target){
            if (mS>=mE && nS>=nE) return matrix[mS][nS]==target;
            int m=matrix.length;
            int n=matrix[0].length;
            int a = mE;
            int b = mS;
            int c = nS;
            int d = nE;
            if(mS<mE){
                a=searchM(matrix, nS, mS, mE, target);
                if (matrix[a][nS]==target) return true;
                a= matrix[a][nS]<target ? a : a>0 ? a-1 : 0; 
            
                b=searchM(matrix, nE, mS, mE, target);
                if (matrix[b][nE]==target) return true;
                b= matrix[b][nE]>target ? b : b<m-1 ? b+1 : m-1; 
            }
            if(nS<nE){
                c=searchN(matrix, a, nS, nE, target);
                if (matrix[a][c]==target) return true;
                c= matrix[a][c]>target ? c : c<n-1 ? c+1 : n-1; 
            
                d=searchN(matrix, b, nS, nE, target);
                if (matrix[b][d]==target) return true;
                d=matrix[b][d]<target ? d : d>0 ? d-1 : 0;
            }
            return search2D(matrix, b, a, c, d, target);
        }
        
        private int searchM(int[][] matrix, int j, int mS, int mE, int target){
            if (mS>=mE) return mS;
            int mid=mS+(mE-mS)/2;
            if (target>matrix[mid][j]) return searchM(matrix, j, mid+1, mE, target);
            else return searchM(matrix, j, mS, mid, target);
        }
        
        private int searchN(int[][] matrix, int i, int nS, int nE, int target){
            if (nS>=nE) return nS;
            int mid=nS+(nE-nS)/2;
            if (target>matrix[i][mid]) return searchN(matrix, i, mid+1, nE, target);
            else return searchN(matrix, i, nS, mid, target);
        }
    }
    

Log in to reply
 

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