Search in rotated sorted array with duplicates

Baseline Binary Search · 1D Arrays O(log n) average, O(n) worst case when many duplicates hide the sorted side · O(1)

Membership Check in a Wrapped Catalog with Reprints

A parts catalog lists stock codes in ascending order and was wrapped during re-shelving, but this revision contains repeated codes. Repeats make some probes ambiguous about which side is ordered, so the search occasionally must shrink by one slot from both ends instead of halving. Answer whether a requested code is still stocked.

Input: An array nums of n integers sorted in non-decreasing order and then rotated at an unknown pivot, and an integer target.

Output: true when target appears in nums, otherwise false.

Constraints

1 <= n <= 5000
-10^4 <= nums[i] <= 10^4
Values may repeat
Minimize the overall number of probe steps

Examples

Example 1

Input: {"nums":[2,5,6,0,0,1,2],"target":0}
Output: true
The code 0 survives the re-shelve and is found despite the wrap.

Example 2

Input: {"nums":[2,5,6,0,0,1,2],"target":3}
Output: false
Code 3 is not stocked anywhere in the wrapped catalog.

Solve this in your browser →

Also on LeetCode ↗