mediumCodingMidSeniorStaff
You are given a sorted array that has been rotated by an unknown amount. Find a target value in logarithmic time.
Search a rotated sorted array in O(log n) by finding which half is sorted at each midpoint, then keeping the half where the target can legally fall. With duplicates, equal endpoints can hide the pivot, so the worst case becomes linear.
5 min readUpdated 2026-08-15Target archetype: Big Tech, Enterprise Captive, Product Startup
Answer
Short answer
Use modified binary search. At each midpoint, one side of a rotated sorted array is still sorted; test whether the target lies inside that sorted side and discard the other side. This stays O(log n) for distinct values, but duplicates can make the sorted-side test ambiguous and force O(n) worst-case probing.
Was this answer helpful?
Likely follow-ups
- Find the minimum element instead of a target. What does the same comparison give you?
- How many rotations were applied? Can you recover that number?
- The array is rotated and also contains duplicates. What is the worst case, and can you prove nothing does better?
- The array is rotated twice, by two different amounts, over two halves. Does any of this survive?
Related questions
- Find the rotation point of a rotated sorted array, then do it again when the array has duplicates.mediumAlso on rotated-array and binary-search4 min
- Given package weights in a fixed order, find the smallest ship capacity that delivers them all within D daysmediumAlso on binary-search and invariants5 min
- Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?hardAlso on binary-search4 min
- You may use an AI coding assistant in the machine-coding round. What do you still write yourself, and what do you ask it for?mediumAlso on invariants5 min