LeetCode-81. Search in Rotated Sorted Array II

一、问题描述

　　这是问题33的升级版，在数组中有重复元素。

二、问题解决

　　思路和问题33一样，不同点在于判断nums[left]==nums[middle]的时候不能得出左右哪个是单调递增，哪个是循环递增。这时候简单递增一下left，应为此时left一定不为target，可以使代码进一步往下运行。

 1 bool search_duplicates(vector<int>& nums, int target) {
 2     int left = 0;
 3     int right = nums.size() - 1;
 4     while (left <= right) {
 5         int middle = (left + right) / 2;
 6         if (nums[middle] == target)
 7             return true;
 8         if (nums[middle] > nums[left])
 9             if (target <= nums[middle] && nums[left] <= target)
10                 right = middle - 1;
11             else
12                 left = middle + 1;
13         else if (nums[middle] < nums[left])
14             if (target >= nums[middle] && nums[right] >= target)
15                 left = middle + 1;
16             else
17                 right = middle - 1;
18         else
19             left++;
20     }
21     return false;
22 }
23 
24 int main()
25 {
26     vector<int> v = { 4, 5, 6, 7,7, 0, 1, 2 };
27     cout << search(v, 7) << endl;
28 
29     system("pause");
30     return 0;
31 }

　　和33相比，只有18行和19行多了一个等于时的条件判断，然后前面把等于的条件去掉了，调整了if esle。