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.
題意：把一個(gè)有序數(shù)組做旋轉(zhuǎn)禽篱，比如1234變成3412白粉，要判斷一個(gè)給定的數(shù)字在不在數(shù)組中阻荒，并且這個(gè)數(shù)組可能有重復(fù)的值。這道題是Search in Rotated Sorted Array的followup，加的條件就是會(huì)有重復(fù)值。
思路：先說(shuō)原題Search in Rotated Sorted Array，這道題用二分法可以解決来累。
對(duì)于一個(gè)rotate的有序數(shù)組，中間的值要么大于起始位置要么小于起始位置窘奏，如果大于起始位置嘹锁，那么起始位置到中間這部分是升序，如果要找的數(shù)字在這段升序區(qū)間內(nèi)着裹，則中間到結(jié)尾這部分就可以不用考慮了领猾；如果小于起始位置，那么中間到結(jié)尾位置是升序骇扇，如果要找的數(shù)字在這段升序區(qū)間摔竿，那么起始到中間這段就不用考慮了。
比如數(shù)組是34512少孝，要找的數(shù)字是1继低。
第一次二分，中間的值是5稍走，1不在3到5區(qū)間內(nèi)袁翁，所以起始位置指向5。
目前查找的范圍變成了512婿脸。
第二次二分粱胜，中間位置是1，1就是target狐树，返回true焙压。
而本題有重復(fù)數(shù)字，極端情況1111101抑钟，找0涯曲，第一次二分中間值1和首位無(wú)法比較大小來(lái)判斷舍棄那部分區(qū)間，這種情況只能移動(dòng)待比較的左邊界在塔，期望下次能進(jìn)行二分幻件。
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;
}