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
numsmay contain duplicates. - Would this affect the run-time complexity? How and why?
AC代碼
class Solution {
public:
bool search(vector<int>& nums, int target) {
if (nums.empty()) return false;
int left = 0, right = nums.size() - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (nums[mid] == target) return true;
if (nums[left]==nums[right]) left++; //或者right--
else if (nums[mid] >= nums[left]) { // mid左邊有序
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
}
else if (nums[mid] <= nums[right]) { // mid右邊有序
if (target >= nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return false;
}
};
總結(jié)
這個(gè)題與33題唯一的不同是左右兩端的值可能相同炬称，修改方法是當(dāng)這種情況發(fā)生時(shí)阳掐，執(zhí)行一次left++或者right--操作
