My solution with O(logn) time


  • 0
    B
    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;
            }
            
        }
        
        bool 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 true;
            }
            return false;
        }
    
        bool search(int A[], int n, int target) {
            return FindIndex(A, n, target);
        }
    };

  • 0
    S

    if an array are full of the same number like

    [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
    

    and we want to find whether 2 is in it.
    Is your algorithm still O(logN)?
    my code is similar with yours, but I think it will cost O(NlogN) or O(N) ( I'm not quite sure :D)facing this condition.


Log in to reply
 

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