TLE for O(logn)


#1

This O(logn) solution is not working for some reason. Finding the pivot first and then searching for the element on both sides of the pivot.

int findPivotIndex(const vector<int> &A)
{
    int low=0, high=A.size()-1;
        
    while(low<=high)
    {
        if(A.at(low)<A.at(high))//already sorted
            return low;
            
        int mid=(low+high)/2;
        int prev=(mid-1+A.size())%A.size();
        int next=(mid+1)%A.size();
        
        if(A.at(mid)<A.at(prev) && A.at(mid)<A.at(next))
            return mid;
        else if(A.at(mid)>A.at(low))//go right
            low=mid+1;
        else if(A.at(mid)<A.at(high))//go left
            high=mid-1;
    }
}

int binarySearch(const vector<int> &A, int B, int pivotIndex, bool searchLeft)
{
    int low, high;
    if(searchLeft)
    {
        low=0;
        high=pivotIndex-1;
    }
    else
    {
        low=pivotIndex+1;
        high=A.size()-1;
    }
       
    while(low<=high)
    {
        int mid=(low+high)/2;
        if(A.at(mid)==B)
            return mid;
        else if(A.at(mid)<B)
            low=mid+1;
        else
            high=mid-1;
    }
    
    return -1;
}

int Solution::search(const vector<int> &A, int B) {
    int pivotIndex=findPivotIndex(A);
    if(A.at(pivotIndex)==B)
        return pivotIndex;

    int index;
    index=binarySearch(A, B, pivotIndex, true);
    if(index!=-1)
        return index;
    index=binarySearch(A, B, pivotIndex, false);
    return index;
}