My solution with O(logn), no matter what duplicate or not.


  • 0
    B
    1. find the pivot int a[],for example, a[]={4,5,6,7,0,1,2},we can find the pivot number is “0”,so the pivot is 4.
    2. if target is more than a[0], binary search in {4,5,6,7}, else binary search in {0,1,2}.
    class Solution {
    
        public:
        int FindPivot( int a[], int start, int end )
        {
            if ( start == end )
                return -1;
                
            if ( start+1 == end ) {
                if ( a[start] > a[end] )
                    return end;
                else
                    return -1;
            }
            int mid = ( start + end ) / 2; 
                 
            if ( a[mid] > a[start] )
                return FindPivot( a, mid, end );
                
            else if ( a[mid] < a[start] )
                return FindPivot( a, start, mid );
                
            else {
                int p = FindPivot( a, start, mid );
                int q = FindPivot( a, mid, end );
                if ( p != -1 )
                    return p;
                if ( q != -1 )
                    return q;
                return -1;
            }
            
        }
        
        int FindIndex ( int a[], int n ,int target)
        {
            int pos = FindPivot(a,0,n-1);
            int start, end, mid;
            if ( pos == -1 ) {
                start = 0;
                end = n-1;
            }
            else {
                if ( target < a[0] ) {
                    start = pos;
                    end = n-1;
                }
                else {
                    start = 0;
                    end = pos-1;
                }
            }
            while( start <= end )
            {
                mid = ( start + end ) / 2;
                if ( a[mid] < target )
                    start = mid + 1;
                else if ( a[mid] > target )
                    end = mid - 1;
                else
                    return mid;
            }
            return -1;
        }
    
        int search(int A[], int n, int target) {
            return FindIndex(A, n, target);
        }
    };

  • 4
    S

    I think this is not an O(lgN) solution due to this else block:

    else {
            int p = FindPivot( a, start, mid );
            int q = FindPivot( a, mid, end );
            if ( p != -1 )
                return p;
            if ( q != -1 )
                return q;
            return -1;
        }
    

    Consider the array: {2,2,2,2,2}, the else block will visit all the indexes. So this solution is O(N). Please correct me if I am wrong.


  • 0
    B

    you are right. the worst time complexity is O(n)


Log in to reply
 

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