# My solution with O(logn), no matter what duplicate or not.

1. find the pivot int a[]，for example, a[]={4,5,6,7,0,1,2}，we can find the pivot number is “0”，so the pivot is 4.
2. if target is more than a[0], binary search in {4,5,6,7}, else binary search in {0,1,2}.
``````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;
}

}

int 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 mid;
}
return -1;
}

int search(int A[], int n, int target) {
return FindIndex(A, n, target);
}
};``````

• I think this is not an O(lgN) solution due to this else block:

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

Consider the array: {2,2,2,2,2}, the else block will visit all the indexes. So this solution is O(N). Please correct me if I am wrong.

• you are right. the worst time complexity is O(n)

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