C++ solution using STL in O(logn)

programming
Tags: #<Tag:0x00007f1828556850>

#1

int find_pivot(vector&A)
{
if(A[0]>A[1])
return 1;
if(A[A.size()-1]<A[A.size()-2]&&A[A.size()-3]<A[A.size()-2])
return A.size()-1;
int left=0;
int right=A.size()-1;
while(left<=right)
{
int mid=(left+right)/2;
if(A[mid]>A[mid+1]&&A[mid-1]>A[mid])
return mid;
else if(A[mid]>A[left])
left=mid+1;
else
right=mid-1;
}
}
int Solution::solve(vector &A, int B) {
int pivot=find_pivot(A);
if(binary_search(A.begin(),A.begin()+pivot-1,B))
{
return lower_bound(A.begin(),A.begin()+pivot-1,B)-A.begin();
}
else if(binary_search(A.begin()+pivot-1,A.end(),B,greater()))
{
return lower_bound(A.begin()+pivot-1,A.end(),B,greater())-A.begin();
}
return -1;
}