81. 搜索旋转排序数组 II.png
二分查找
class Solution {
public boolean search(int[] nums, int target) {
int n = nums.length;
if (n == 0) return false;
if (n == 1) return nums[0] == target;
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
// cannot judge the area
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
left++;
right--;
} else if (nums[left] <= nums[mid]) {
// left to mid area is ordered
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// mid to right area is ordered
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
}
