本文主要是介绍leetcode No81. Search in Rotated Sorted Array II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Question：
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.
在旋转数组中找target，与I不同的是，这次存在重复元素
Algorithm：
先找顺序，再找target
有三种情况:（至少有一半是顺序的）
1、nums[mid]==target
2、nums[l]<nums[mid](左半是顺序，如果target在范围内，二分，如果不在，则在右半找顺序，即重复1，2，3)
3、nums[l]>nums[mid](右半是顺序，如果target在范围内，二分，如果不在，则在左半找顺序，则重复1，2，3)
4、nums[l]>nums[mid]（不确定左边是否为重复，只能往前一步 ）
Accepted Code:
class Solution {
public:bool search(vector<int>& nums, int target) {int res=-1;int l=0;int r=nums.size()-1;int mid=0;while(l<=r){int mid=l+(r-l)/2;if(nums[mid]==target)return true;else if(nums[l]<nums[mid]) //mid左边是顺序{if(nums[l]<=target&&nums[mid-1]>=target) r=mid-1;elsel=mid+1;}else if(nums[l]>nums[mid]) //mid右边是顺序{if(nums[mid+1]<=target&&nums[r]>=target) l=mid+1;else r=mid-1;}else //不确定左边是否为重复，只能往前一步l++;}if(nums[mid]==target)return true;else return false; }
};
这篇关于leetcode No81. Search in Rotated Sorted Array II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
