class Solution {
public:
bool search(int A[], int n, int target) {
int lo =0, hi = n1;
int mid = 0;
while(lo<hi){
mid=(lo+hi)/2;
if(A[mid]==target) return true;
if(A[mid]>A[hi]){
if(A[mid]>target && A[lo] <= target) hi = mid;
else lo = mid + 1;
}else if(A[mid] < A[hi]){
if(A[mid]<target && A[hi] >= target) lo = mid + 1;
else hi = mid;
}else{
hi;
}
}
return A[lo] == target ? true : false;
}
};
C++ concise log(n) solution


Your solution is very nice, this is my Python implementation of it:
def search(nums, target): lo, hi = 0, len(nums)1 while lo < hi: mid = lo + (hi  lo)/2 if nums[mid] == target: return True if nums[mid] > nums[hi]: if nums[lo] <= target < nums[mid]: hi = mid else: lo = mid + 1 elif nums[mid] < nums[hi]: if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid else: hi = 1 return lo < len(nums) and nums[lo] == target

I think, this is not completely correct. For example [3, 1], target = 1, since "hi" can cause wrong answer.
Here is my solution.
http://paste.ubuntu.com/16914208/class Solution { public: int search(vector<int> & nums, int target) { int l = 0, r = nums.size()  1; while (l <= r) { int mid = (r  l) / 2 + l; if (target == nums[mid]) { return true; } else if (nums[l] <= nums[mid]) { if (nums[l] == nums[mid]) ++l; else if (target >= nums[l] && target < nums[mid]) { r = mid  1; } else l = mid + 1; } else if (nums[mid] <= nums[r]) { if (nums[mid] == nums[r]) r; else if (target > nums[mid] && target <= nums[r]) { l = mid + 1; } else r = mid  1; } else while (1) ; } return false; } };

That's because you are comparing mid with high, not mid with low in "if" statements.
If num[mid] == num[high], it can be proved that num[high] can be discarded safely, but nothing can say about num[low]
 you didn't even check what value num[low] has, how dare you directly discarded it by "low ++".
Then you may ask, if you use "num[mid] == num[low]" as the condition, can you use low ++?
The answer is also NO. The reason is you can't know for sure which direction you go by just checking against num[low]
Why so? This is because this array may be rotated and may be not. For rotated array, checking mid against low or high has same effect,
but for unrotated array, you should always go to left (minimum is the first one), and checking low would make you go to the other direction.
Checking high will automatically make you go all the way to the left. In other words, if you use high as the condition, it is same for both
rotated array and unrotated array, but if you use low, the two cases have opposite conditions.

bool search(vector<int>& nums, int target) { int len = nums.size(); int start = 0, end = len  1; while (start <= end){ int mid = start + (end  start)/2; if (nums[mid] == target) return true; if (nums[mid] > nums[start]){ if (nums[mid] > target && nums[start] <= target) end = mid; else start = mid + 1; }else if (nums[mid] < nums[start]){ if (nums[mid] < target && nums[end] >= target) start = mid + 1; else end = mid; }else start ++; } return false; }

@fentoyal said in C++ concise log(n) solution:
That's because you are comparing mid with high, not mid with low in "if" statements.
If num[mid] == num[high], it can be proved that num[high] can be discarded safely, but nothing can say about num[low]
 you didn't even check what value num[low] has, how dare you directly discarded it by "low ++".
Then you may ask, if you use "num[mid] == num[low]" as the condition, can you use low ++?
The answer is also NO. The reason is you can't know for sure which direction you go by just checking against num[low]
Why so? This is because this array may be rotated and may be not. For rotated array, checking mid against low or high has same effect,
but for unrotated array, you should always go to left (minimum is the first one), and checking low would make you go to the other direction.
Checking high will automatically make you go all the way to the left. In other words, if you use high as the condition, it is same for both
rotated array and unrotated array, but if you use low, the two cases have opposite conditions.disagree!
It is also a way to use low to checking.
Accept code using low++ ,bool search(vector<int>& nums, int target) { int l = 0, h = nums.size()  1; while (l < h) { int mid = l + (h  l) / 2; if (nums[mid] == target) return true; if (nums[mid] < nums[l]) { if (nums[mid] < target && nums[h] >= target) l = mid + 1; else h = mid  1; } else if (nums[mid] > nums[l]) { if (nums[mid] > target && nums[l] <= target) h = mid  1; else l = mid + 1; } else {////nums[mid] == nums[l] l++; } } return nums[l] == target; }


@rambo2 I think the difference is that you don't need to traverse through the array in most cases so the average time is log(n).