Time limit exceeded ?? Algo runs in O(lg n)


  • 0
    M
    class Solution {
    public:
    
        int search(int a[], int n, int key) {
            int pivot = FindPivot(a,n);
            if(key == a[pivot])
                return pivot;
            int index = binary_search(a,0,pivot-1,key);
            if(index !=-1)
                return index;
            return binary_search(a,pivot+1,n-1,key);
        }
    
     int FindPivot(int a[], int size) {
    
        int low =1, high= size-1, mid;
        if(size ==1)
            return 0;
        while(low < high)
        {
            mid = low +(high-low)/2;
            if( a[mid-1] <= a[mid] && a[mid] <= a[mid +1]) //in ascending order
                low = mid +1;
            else if(a[mid-1] >= a[mid] && a[mid] >= a[mid+1])
                high = mid -1;
            else if(a[mid] > a[mid-1] && a[mid] > a[mid+1])
                break;
        }
        if(high ==0)
            low = high;
        return low;
    }
    
    int binary_search(int a[], const int left, const int right, const int key){
    
        static int index = -1, mid;
       
        if(left > right || left < 0 ) // Error case
             return index;    
    
        mid = left + (right - left)/2;
    
        if(a[mid] == key)
            index = mid;
        else if(key < a[mid])
            binary_search(a,left,mid-1,key);
        else
            binary_search(a,mid+1,right, key);
        return index;
    }
    
    };

  • 0
    S

    Hi @mridul, thanks for your post. Just corrected your code format.


  • 0
    M

    Thanks @Shagrila


  • 0
    Y

    When trying to locate the pivot, the worst is that you go over all items in the array (when the pivot is array[0] or array[array.length - 1]. Try modify your pivot locating. (Suggest to think over if it is necessary to locate the pivot also.)


Log in to reply
 

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