共计 1203 个字符，预计需要花费 4 分钟才能阅读完成。
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).You are given a target value to search. If found in the array return true, otherwise return false.Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?
难度：medium
题目：假设一个按升序排序的数组在某个未知的轴上旋转。搜索给定目标值，如果找到返回 true，否则返回 false。
思路：二叉搜索。分 4 种情况。
case 1：从头到尾升序。
case 2：从头到尾降序。
case 3：升序的元素多，降序少。
case 4：升序的元素少，降序多。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array II.Memory Usage: 37.6 MB, less than 1.00% of Java online submissions for Search in Rotated Sorted Array II.
class Solution {
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length – 1;
while (left <= right) {
int mid = left + (right – left) / 2;
if (target == nums[mid]) {
return true;
}
// left < mid </> right
if (nums[left] < nums[mid]) {
if (target > nums[mid] || target < nums[left]) {
left = mid + 1;
} else {
right = mid – 1;
}
} else if (nums[left] > nums[mid]) {// left > mid </> right
if (target < nums[mid] || target > nums[right]) {
right = mid – 1;
} else {
left = mid + 1;
}
} else {// left = mid
left += 1;
}
}
return false;
}
}
