Find in a Rotated Roster
MediumBinary Search
Problem
A roster of distinct employee badge numbers was sorted in increasing order and then rotated at an unknown pivot: some prefix was moved to the end. For example [1, 3, 4, 6, 9, 12] may become [6, 9, 12, 1, 3, 4].
Given the rotated array badges and a number target, return the index of target, or -1 if it is absent. Your algorithm must run in O(log n) time.
Example 1
- Input:
- badges = [6, 9, 12, 1, 3, 4], target = 3
- Output:
- 4
Example 2
- Input:
- badges = [6, 9, 12, 1, 3, 4], target = 7
- Output:
- -1
Example 3
- Input:
- badges = [5], target = 5
- Output:
- 0
Constraints
- 1 ≤ badges.length ≤ 10^5
- -10^9 ≤ badges[i], target ≤ 10^9
- All values are distinct.
- The rotation may be by zero positions.
Hint
Show the first hint
Cut a rotated sorted array at any mid. Is at least one of the two halves guaranteed to be sorted?
Walkthrough
How to approach it
01Clarify before coding
- Are the values distinct? Yes; duplicates would break the 'which half is sorted' test.
- Can the array be not rotated at all? Yes, rotation by 0 is allowed.
- What if target is missing? Return -1.
02Brute force
Linear scan; or find the rotation point first and then run a normal binary search on the right part.
Cost: The scan is O(n). The two-pass idea is O(log n) and fine, but it takes two searches and more code than needed.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.