LeetCode 81. Search in Rotated Sorted Array II

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.
Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:

This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?
解析：
此题目是在LeetCode 33 数组循环移位基础上做了更改，之前限制数组无重复元素，这个题目允许重复元素的存在。这样会影响判断哪半边是有序的，比如[1,1,3,1]和[3,1,1],当nums[mid] == nums[high]时，只需要把最右一位向左移动一位即可。具体代码跟上个题目类似。
[cc lang=”C++”]
class Solution {
public:
bool search(vector& nums, int target) {
int low = 0, high = nums.size()-1;
while(low <= high) { int mid = low + (high-low)/2; if(nums[mid] == target) return true; if(nums[mid] < nums[high])//右半边有序 { if(nums[mid] < target && nums[high] >= target)
low = mid + 1;
else
high = mid -1;
}else if(nums[mid] > nums[high])
{
if(nums[mid] > target && nums[low] <= target) high = mid -1; else low = mid +1; }else high --;//相等，最右值左移一位 } return false; } }; [/cc] 运行结果：
参考：
https://www.cnblogs.com/grandyang/p/4325840.html