Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false
现在，假设数组中的元素不会重复。 （1）当mid < < <script type="math/tex" id="MathJax-Element-159"><</script>right 的元素的时候，如果mid < < <script type="math/tex" id="MathJax-Element-160"><</script>target ≤ ≤ right中的元素的时候，可以得知元素在[mid,right]范围内，因此可以在这个区间内查找target。否则说明target在另一侧，令right = mid-1即可。 （2）当mid>left的时候，如果left ≤ ≤ target < < <script type="math/tex" id="MathJax-Element-163"><</script>mid的时候，可以得知元素在[left,mid]中，可以在此范围中查找。否则说明在另一半范围中，此时令left = mid+1。 （3）当mid==target的时候，返回true。
这道题目和之前的Search in Rotated Sorted Array的区别在于，本题目中数组元素可以重复。这样就增加了寻找难度。具体体现在，假设现在有旋转后的数组nums = {2,0,2,2,2}，这时候left、mid和right的元素相同，无法判断应该跳向哪一侧。此时较好的办法时，将left+1，将right-1，继续缩小查找范围。
值得说明的是，上述代码也适用于没有重复元素的rotated Array中target的查找。
class Solution { public: bool search(vector<int>& nums, int target) { int left = 0, right = nums.size()-1, mid; while(left<=right) { mid = (left + right) >> 1; if(nums[mid] == target) return true; // the only difference from the first one, trickly case, just updat left and right if( (nums[left] == nums[mid]) && (nums[right] == nums[mid]) ) {++left; --right;} else if(nums[left] <= nums[mid]) { if( (nums[left]<=target) && (nums[mid] > target) ) right = mid-1; else left = mid + 1; } else { if((nums[mid] < target) && (nums[right] >= target) ) left = mid+1; else right = mid-1; } } return false; } };