本文共 1525 字，大约阅读时间需要 5 分钟。
本系列文章已全部上传至我的github，地址：
欢迎大家关注我的新浪微博， 欢迎转载，转载请注明出处
Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
题目大意：在旋转过的有序数组中查找一个指定值。
可以参考在I的基础上，允许数组中的数重复，那么针对这种情况3，4，3就只能一个一个查找了，没办法用二分来查找。
除上述特殊情况，都可以先确定数组的旋转中心，即最大值和最小值的交界。
然后确定目标数属于那一边，再用二分法查找。class Solution {public: bool search(vector & nums, int target) { int len = nums.size(); int i = 0; int j = len - 1; int p = 0; bool isfind = false; if(nums[0]==nums[len-1]){ //数组头尾相等属于特殊情况，只能挨个查找了 return find(nums.begin(),nums.end(),target)!=nums.end(); } if (nums[0]>nums[len-1])//一般情况 { while (i < j)//二分法找出最大值和最小值的交界 { if (i == j - 1) { isfind = true; break; } int mid = (i + j) / 2; if (nums[i] <= nums[mid]) i = mid; if (nums[j] >= nums[mid]) j = mid; } } if (isfind)//如果找到了，就确认目标数所在的分区 { if (nums[0] <= target) { j = i; i = 0; } if (nums[len - 1] >= target) { i = j; j = len - 1;} } while (i<=j)//在分区中采用二分法来查找 { int mid = (i + j) / 2; if (nums[mid] == target) return true; else if (nums[mid] >target) j = mid-1; else i = mid+1; } return false; }};