# My solution with O(logn) time

• ``````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);
}
};``````

• 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.