O(2*logn) solution won't work


#1

Using one binary search for pivot and another for finding the element won’t work. Try to do everything within one binary search.


#2

First finding pivot then finding element will work, just be wary of the boundary cases. Here is my code that gave successful submission

int binSearch(vector A, int B, int start, int end){
if(end < start) return -1;
if(end == start){
if(A[start] == B)
return start;
else
return -1;
}

int low = start, high = end;
while(A[low] <= A[high]){
    int mid = (low + high) / 2;
    if(A[mid] == B) 
        return mid;
    else if(A[mid] < B) 
        low = mid + 1;
    else 
        high = mid - 1;
}
return -1;

}
int Solution::search(const vector &A, int B) {
int n = A.size(), low, high, pivot = 0, mid;
bool isSorted = true;
if(A[0] >= A[n-1]){
isSorted = false;
low = 0; high = n-1;
while(A[low] >= A[high]){
mid = (low + high) / 2;
// cout << low << “-” << mid << “-” << high << endl;
if(A[mid] >= A[low]) low = mid + 1;
else high = mid;
if(low == high) break;
}
// cout << "Final: " << low << “-” << mid << “-” << high << endl;
pivot = low;
}
// cout<< "Pivot: " << pivot<< endl;
if(pivot == 0 && isSorted)
return binSearch(A, B, 0, n-1);
else if(pivot == 0 && !isSorted){
if(A[0] == B)
return 0;
else
return -1;
}
else{
if(B <= A[pivot - 1] && B >= A[0])
return binSearch(A, B, 0 , pivot - 1);
else
return binSearch(A, B, pivot, n - 1);
}
}