线性探测+二分查找

本题和 力扣(LeetCode)33. 搜索旋转排序数组(C++) 的唯一区别是有重复元素，思考我们之前的二分条件，是根据 nums[0]nums[0]nums[0] 和 nums[mid]nums[mid]nums[mid] 判断 midmidmid 哪一端有序，但是现在可能出现 nums[0]=nums[mid]=nums[r]nums[0]=nums[mid] =nums[r]nums[0]=nums[mid]=nums[r] ，再按照 nums[mid]nums[mid]nums[mid] 和 nums[0]nums[0]nums[0] 判断有序，已经不成立了。考虑去除 numsnumsnums 末尾等于 nums[0]nums[0]nums[0] 的数，避免特例，这样就可以按照 333333 题那样二分了。

class Solution {
public:bool search(vector& nums, int target) {int r = nums.size()-1;while(r>=0&&nums[0]==nums[r]) r--;if(r<0) return nums[0]==target;int l = 0;while(l<=r){int mid = l+((r-l)>>1);if(nums[0]<=nums[mid]){//左端有序if(target>=nums[0]&&nums[mid]>=target) r = mid -1;else l = mid + 1;}else{if(target