第81题：搜索旋转排序数组Ⅱ

题目描述：

已知存在一个按非降序排列的整数数组nums，数组中的值不必互不相同。

在传递给函数之前，nums在预先未知的某个下标k(0<=k<nums.length)上进行了旋转，使数组变为nums[k]，nums[k+1],......nums[n-1]，nums[0]，nums[1],......nums[k-1]（下标从0开始计数）。例如【0 1 2 4 4 4 5 6 6 7】在下标5处旋转后可能变为【4 5 6 6 7 0 1 2 4 4】

给你旋转后的数组nums和一个整数target，请你编写一个函数来判断给定的目标值是否存在于数组中，如果nums中存在这个目标值target，则返回true，否则返回false。

你必须尽可能减少整个操作步骤。

示例1：

输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例2：

输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

提示：

1 <= nums.length <= 5000
-10的4次方 <= nums[i] <= 10的4次方
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-10的4次方 <= target <= 10的4次方

题解：

方法一：遍历法

bool search(int* nums, int numsSize, int target){for(int i=0;i<numsSize;i++){if(nums[i]==target) return true;}return false;
}

方法二：二分查找，为避免重复数字，增加条件选项。

可以尝试将重复数字首先去除。

bool search(int* nums, int numsSize, int target) {if (numsSize == 0) {return false;}if (numsSize == 1) {return nums[0] == target;}int l = 0, r = numsSize - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) {return true;}if (nums[l] == nums[mid] && nums[mid] == nums[r]) {++l;--r;} else if (nums[l] <= nums[mid]) {if (nums[l] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[numsSize - 1]) {l = mid + 1;} else {r = mid - 1;}}}return false;
}