//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: binarysearch
class Solution {
public:
bool search(int A[], int n, int target) {
int first=0,last=n1,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=mid1;
else if(A[last]==A[mid])//we can't judge left or right is ok
last;
else{
if(A[first]<=target)
last=mid1;
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=mid1;
}
}
}
return false;
}
};
Why the runtime complexity is still O(logn) in search in rotated sorted array 2 with binary search method?


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 n1. 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 nonexistence 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.