# Why the run-time complexity is still O(logn) in search in rotated sorted array 2 with binary search method?

• ``````//1st: violent search
class Solution {
public:
bool search(int A[], int n, int target) {
int k;
for(k=0;k<n;k++){
if(A[k]==target){
return true;
}
}
return false;
}
};

//2nd: binary-search
class Solution {
public:
bool search(int A[], int n, int target) {
int first=0,last=n-1,mid;
while(first<=last){
mid=(first+last)/2;
if(A[mid]==target)
return true;
else if(A[mid]>target){
if(A[last]>A[mid])
last=mid-1;
else if(A[last]==A[mid])//we can't judge left or right is ok
last--;
else{
if(A[first]<=target)
last=mid-1;
else
first=mid+1;
}
}
else{
if(A[first]<A[mid])
first=mid+1;
else if(A[first]==A[mid])//we can't judge left or right is ok
first++;
else{
if(A[last]>=target)
first=mid+1;
else
last=mid-1;
}
}
}
return false;
}
};``````

• Assume you have an array entirely composed of one number, i.e. [3,3,3,3,3,3,3,3,3,3,3] and you are searching for 4.

In each loop, A[mid] != 4, and A[mid] < 4, so the final else is run. Then A[first] == A[mid], so the else if is run, incrementing first by 1. This repeats, shrinking the effective array by 1 each time until you have first>last, which will take `last` loops, or n-1. Therefore, in the worst case, this is not O(logn), but O(n) time complexity.

Because of this worst case, there is no way to determine the existence or non-existence of the target in less than O(n) time. The rotation could be at any position, so you cannot skip any number until you have different beginnings and ends. Since you never will, you cannot skip any of the n numbers, giving a lower bound of O(n) time.

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