题目：
已知存在一个按非降序排列的整数数组 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
- -104 <= nums[i] <= 104
- 题目数据保证 nums 在预先未知的某个下标上进行了旋转
- -104 <= target <= 104
进阶：
- 这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
- 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：
注意：这里面有重复元素，对于像[1,3,1,1,1]这种数组，很难通过nums[left]和nums[mid]比较来判断两个升序区间的位置，但是可以通过比较nums[mid]与nums[left]是否相同，来排除重复数字，如果nums[mid] == nums[left]说明有重复的数字，让left向右移动来排除重复数字。
题目中说将数据进行旋转，这样的话就会将搜索区间从中间一分为二，位于中间的元素nums[mid]一定会在其中一个有序的区间中。当nums[mid]与target相等时，直接返回true。后续不等的情况，讨论mid与左边界的大小关系，分为两种情况：
1.mid的值大于等于左边界时：nums[mid] >= nums[left]
- 此时在区间[left, mid - 1]内的元素一定是有序的，如果target在[left, mid -1]里，即nums[left] <= target < nums[mid]，此时设置right = mid - 1;
- 上一个区间的反面，target在区间[mid, right]中，left == mid；
2.mid的值小于左边界时：nums[mid] < nums[left]
- 此时在区间[mid, right]内的元素一定是有序的，为了两种情况left和right变化一致，这里是假设如果target在[mid, right]里，即nums[mid] <= target <=nums[right]，此时设置left = mid ;
- 上一个区间的反面，target在区间[left, mid - 1]中，right == mid - 1；
注意：这里的区间存在[mid, right]，为了防止区间只有两个元素的时候，向下取整会让mid一直和left相同，出现死循环，故需要变成向上取整mid = left + (right - left + 1) / 2。
java代码（left < right）：
1 class Solution {
2 public boolean search(int[] nums, int target) {
3 int left = 0, right = nums.length - 1;
4 while (left < right){
5 int mid = left + (right - left + 1) / 2;
6 if (nums[mid] == target) return true;
7 if (nums[left] == nums[mid]){
8 left++;
9 continue;
10 }
11 if (nums[mid] >= nums[left]){
12 if (target < nums[mid] && target >= nums[left]){
13 right = mid - 1;
14 }else{
15 left = mid;
16 }
17 }else{
18 if (target >= nums[mid] && target <= nums[right]){
19 left = mid;
20 }else{
21 right = mid - 1;
22 }
23 }
24 }
25 return nums[left] == target;
26 }
27 }
python代码：
1 class Solution: 2 def search(self, nums: List[int], target: int) -> bool: 3 left, right = 0, len(nums) - 1 4 while left < right: 5 mid = left + (right - left + 1) // 2 6 if nums[mid] == target: 7 return True 8 if nums[left] == nums[mid]: 9 left += 1 10 continue 11 if nums[mid] >= nums[left]: 12 if nums[left] <= target < nums[mid]: 13 right = mid - 1 14 else: 15 left = mid 16 else: 17 if nums[mid] <= target <= nums[right]: 18 left = mid 19 else: 20 right = mid - 1 21 return True if nums[left] == target else False
java代码（left <= right）：
1 class Solution {
2 public boolean search(int[] nums, int target) {
3 int left = 0, right = nums.length - 1;
4 while (left <= right){
5 int mid = left + (right - left) / 2;
6 if (nums[mid] == target) return true;
7 if (nums[left] == nums[mid]){
8 left++;
9 continue;
10 }
11 //左边有序
12 if (nums[mid] >= nums[left]){
13 if (target < nums[mid] && target >= nums[left]){
14 right = mid - 1;
15 }else{
16 left = mid + 1;
17 }
18 }else{
19 if (target > nums[mid] && target <= nums[right]){
20 left = mid + 1;
21 }else{
22 right = mid - 1;
23 }
24 }
25 }
26 return false;
27 }
28 }
