Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
解题思路：
参考Java for LeetCode 033 Search in Rotated Sorted Array修改下代码即可，JAVA实现如下：
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
if (target == nums[(right + left) / 2])
return true;
// 右半部分为旋转区域
if (nums[(right + left) / 2] > nums[left]) {
if (target >= nums[left] && target < nums[(right + left) / 2])
right = (right + left) / 2 - 1;
else
left = (right + left) / 2 + 1;
}
// 左半部分为旋转区域
else if (nums[(right + left) / 2] < nums[left]) {
if (target > nums[(right + left) / 2] && target <= nums[right])
left = (right + left) / 2 + 1;
else
right = (right + left) / 2 - 1;
}
// 老实遍历
else
left++;
}
return false;
}