Search in Rotated Sorted Array II
Medium · Binary Search · Array · Binary Search
Problem
An array sorted in non-decreasing order has been rotated at an unknown point: some prefix was moved to the end, so [1,2,2,4,5,6] might now be [4,5,6,1,2,2]. Unlike the classic version of this problem, nums may contain repeated values.
Given nums and an integer target, return true if target appears in nums, and false otherwise.
Look at as few elements as you can, and think about how repeated values change the worst case.
Examples
Input: nums = [4,4,5,1,2,4], target = 2 Output: true
2 is at index 4, in the second sorted run.
Input: nums = [4,4,5,1,2,4], target = 3 Output: false
3 is not in the array.
Input: nums = [1,1,1,3,1], target = 3 Output: true
The ends and the middle are all 1, which hides where 3 is, but it is there.
Constraints
- 1 <= len(nums) <= 5000
- -10^4 <= nums[i], target <= 10^4
- nums is a non-decreasing array that may have been rotated
Approaches
- Scan every element — time O(n), space O(1)
Follow-up
Repeats make the worst case linear: in an array of all 1s with a single 2 hidden somewhere, every probe sees 1 at both ends and the middle, and nothing short of looking at each spot can find the 2. The binary search still runs in O(log n) whenever the ends and the middle differ, which is most of the time on real data.
Related problems
Start free on Cariara · Coding problems · System design studio
