← Create New Paste

Search in a Rotated Sorted Array: The Binary Search Variant Interviewers Love

3 views
"Search in rotated sorted array" is a favorite coding interview question because it looks like plain binary search until you try to write it. An ascending array such as [10, 14, 19, 25, 2, 5, 8] has been rotated at an unknown pivot, and you must find a target in O(log n). A linear scan works, but the interviewer is waiting for you to explain why binary search still applies. The key observation When you split a rotated array at mid, at least one half is always sorted. If nums[lo] <= nums[mid], the left half [lo..mid] is in order; otherwise the right half [mid..hi] is. Once you know which half is sorted, you can check with two comparisons whether the target falls inside its range. If it does, search there; if not, it must be in the other half. A clean implementation def search(nums, target): lo, hi = 0, len(nums) - 1 while lo <= hi: mid = (lo + hi) // 2 if nums[mid] == target: return mid if nums[lo] <= nums[mid]: # left half sorted if nums[lo] <= target < nums[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half sorted if nums[mid] < target <= nums[hi]: lo = mid + 1 else: hi = mid - 1 return -1 Walk through [10, 14, 19, 25, 2, 5, 8] with target 5. mid = 3 (25). The left half 10..25 is sorted, and 5 is not inside it, so lo = 4. Now mid = 5 (5) and we are done. Saying an example like this out loud is one of the easiest ways to show the interviewer you understand the invariant rather than having memorized it. Edge cases to mention - The "<=" in nums[lo] <= nums[mid] matters when lo == mid, for example a two-element window. - An array that was never rotated is just a normal sorted array, and the code handles it. - Empty input returns -1 immediately. Common follow-ups 1. Find the minimum (the rotation point). Compare nums[mid] with nums[hi]: if nums[mid] > nums[hi], the minimum is to the right; otherwise it is at mid or to the left. Loop while lo < hi. 2. Duplicates allowed. With [2, 2, 2, 3, 2] you cannot tell which half is sorted when nums[lo] == nums[mid] == nums[hi]. The standard fix is to shrink both ends by one, which keeps correctness but makes the worst case O(n). Saying that trade-off explicitly earns credit. 3. How many times was it rotated? That is simply the index of the minimum. How to present it Start with the brute-force O(n) scan, state the "one half is always sorted" insight, then code it and trace one example. Interviewers mainly grade whether your loop boundaries are consistent, so choose either lo <= hi with mid +/- 1 or lo < hi with hi = mid, and stick to it. If you practice these variants and still freeze when a live interviewer changes the constraints, Linkjob AI (https://linkjob.ai) gives real-time help during job interviews and technical interviews, so you can keep your reasoning on track while you talk through the edge cases.
Created Nov 17, 2026 09:01 Expires Nov 17, 2027 09:01