题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 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
进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
思路
同 搜索旋转排序数组 一样，我们还是采用二分搜索，显然，在我们第一次进行二分的时候，切分的两段数组必然有一个是有序的，在不包含重复元素的情况下，判断这两段数组哪个是有序的是很容易的，我们只需分别比较两段数组的头部和尾部即可，但是在又重复元素的情况下，例如 1,3,1,1,1，切分后得到两段 1,3,1 和 1,1,1 ，我们无法通过比较头部和尾部来判断是否有序，所以一个简单的做法是，将 mid 指针一分为二，mid1 向左移，直到左边这一段数组有序，mid2 向右移，直到右边这个一段数组有序，这样得到的两段数组都是有序的了，接下来直接二分即可；
代码
class Solution {
public boolean search(int[] nums
, int target
) {
int left
= 0, right
= nums
.length
-1;
while (left
<= right
){
int mid
= (left
+right
)/2;
if (nums
[mid
] == target
)
return true;
int mid1
= mid
, mid2
= mid
;
while (mid1
> left
&& nums
[mid1
] <= nums
[left
]) {
mid1
--;
if (nums
[mid1
] == target
)
return true;
}
while (mid2
< right
&& nums
[mid2
] >= nums
[right
]) {
mid2
++;
if (nums
[mid2
] == target
)
return true;
}
if (target
<= nums
[mid1
] && target
>= nums
[left
])
right
= mid1
-1;
else if (target
>= nums
[mid2
] && target
<= nums
[right
])
left
= mid2
+1;
else
break;
}
return false;
}
}
