A sorted array got rotated at an unknown pivot and you still have to find a target in O(log n). The trick is deciding which half is sorted at every step. Here's the clean invariant, and the duplicates follow-up that quietly breaks the log-n promise.
Updated Aug 2026 · Grounded in real Forward Deployed Engineer interview loops and written to a senior-engineer editorial bar.
A sorted array got rotated at an unknown pivot and you still have to find a target in O(log n). The trick is deciding which half is sorted at every step. Here's the clean invariant, and the duplicates follow-up that quietly breaks the log-n promise.
The real signal is whether you can state the loop invariant before coding: at every step one half is sorted, you check whether the target lies inside that sorted half, and you discard the other half. Candidates who pattern-match to 'plain binary search' without handling the pivot get a subtly wrong answer that passes the happy path and fails on the rotated case. The duplicates follow-up is the separator: it forces you to admit O(log n) is no longer guaranteed.
No comments yet — be the first to share your approach.
