题目描述:(链接)
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.
解题思路 :
需要跳过重复的元素。
class Solution { public: bool search(vector<int>& nums, int target) { size_t first = 0; size_t last = nums.size(); while (first != last) { size_t mid = first + (last - first) / 2; if (nums[mid] == target) { return true; } else if (nums[mid] > nums[first]) { // 递增 if (nums[first] <= target && target < nums[mid]) { last = mid; } else { first = mid + 1; } } else if (nums[mid] < nums[first]) {//递减 if (nums[mid] < target && target <= nums[last - 1]) { first = mid + 1; } else { last = mid; } } else {// 跳过重复元素 ++first; } } return false; } };