Why the run-time complexity is still O(logn) in search in rotated sorted array 2 with binary search method?


  • 0
    X
    //1st: violent search
    class Solution {
    public:
        bool search(int A[], int n, int target) {
            int k;
    		for(k=0;k<n;k++){
    			if(A[k]==target){
    				return true;
    			}
    		}
    		return false;
        }
    };
    
    //2nd: binary-search
    class Solution {
    public:
        bool search(int A[], int n, int target) {
            int first=0,last=n-1,mid;
    		while(first<=last){
    		    mid=(first+last)/2;
    			if(A[mid]==target)
    				return true;
    			else if(A[mid]>target){
    				if(A[last]>A[mid])
    					last=mid-1;
    				else if(A[last]==A[mid])//we can't judge left or right is ok
    					last--;
    				else{
    				    if(A[first]<=target)
    				        last=mid-1;
    				    else
    				        first=mid+1;
    				}
    			}
    			else{
    			    if(A[first]<A[mid])
    			        first=mid+1;
    			    else if(A[first]==A[mid])//we can't judge left or right is ok
    			    	first++;
    				else{
    			        if(A[last]>=target)
    			            first=mid+1;
    			        else
    			            last=mid-1;
    			    }
    			}
    		}
    		return false;
        }
    };

  • 2
    M

    Assume you have an array entirely composed of one number, i.e. [3,3,3,3,3,3,3,3,3,3,3] and you are searching for 4.

    In each loop, A[mid] != 4, and A[mid] < 4, so the final else is run. Then A[first] == A[mid], so the else if is run, incrementing first by 1. This repeats, shrinking the effective array by 1 each time until you have first>last, which will take last loops, or n-1. Therefore, in the worst case, this is not O(logn), but O(n) time complexity.

    Because of this worst case, there is no way to determine the existence or non-existence of the target in less than O(n) time. The rotation could be at any position, so you cannot skip any number until you have different beginnings and ends. Since you never will, you cannot skip any of the n numbers, giving a lower bound of O(n) time.


Log in to reply
 

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