Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
题意：把一个有序数组做旋转，比如1234变成3412，要判断一个给定的数字在不在数组中，并且这个数组可能有重复的值。这道题是Search in Rotated Sorted Array的followup，加的条件就是会有重复值。
思路：先说原题Search in Rotated Sorted Array，这道题用二分法可以解决。
对于一个rotate的有序数组，中间的值要么大于起始位置要么小于起始位置，如果大于起始位置，那么起始位置到中间这部分是升序，如果要找的数字在这段升序区间内，则中间到结尾这部分就可以不用考虑了；如果小于起始位置，那么中间到结尾位置是升序，如果要找的数字在这段升序区间，那么起始到中间这段就不用考虑了。
比如数组是34512，要找的数字是1。
第一次二分，中间的值是5，1不在3到5区间内，所以起始位置指向5。
目前查找的范围变成了512。
第二次二分，中间位置是1，1就是target，返回true。
而本题有重复数字，极端情况1111101，找0，第一次二分中间值1和首位无法比较大小来判断舍弃那部分区间，这种情况只能移动待比较的左边界，期望下次能进行二分。
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int left = 0, right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
} else if (nums[mid] > nums[left]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid;
} else {
left = mid;
}
} else if (nums[mid] < nums[left]) {
if (nums[mid] < target && target <= nums[right]) {
left = mid;
} else {
right = mid;
}
} else {
left++;
}
}
return nums[left] == target || nums[right] == target;
}