Search in Rotated Sorted Array II
The key idea
On each step the midpoint splits the array into one half that is still sorted and one that holds the rotation pivot. Compare
nums[mid] against the two ends to find the sorted half, then check whether target falls inside its range to decide which way to go. Duplicates can make nums[lo] == nums[mid] == nums[hi], hiding which half is sorted — when that happens, shrink both ends by one and retry; that single ambiguous case is what degrades the worst case to O(n).Problem
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values). Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length), so that the array becomes [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not.
This is a follow-up to Search in Rotated Sorted Array, where nums may now contain duplicates. You must decide whether those duplicates change the runtime complexity, and explain why.
Constraints
1 <= nums.length <= 5000-10^4 <= nums[i] <= 10^4numsis guaranteed to be rotated at some pivot.-10^4 <= target <= 10^4
Examples
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Binary SearchEASY
- Capacity To Ship Packages Within D DaysMEDIUM
- Find First and Last Position of Element in Sorted ArrayMEDIUM
- Find in Mountain ArrayHARD
- Find K Closest ElementsMEDIUM
- Find Minimum in Rotated Sorted ArrayMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Guess Number Higher or LowerEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD