Search in Rotated Sorted Array

Search in Rotated Sorted Array

What is this problem about?

The Search in Rotated Sorted Array interview question gives you a sorted array that has been rotated at some unknown pivot point (e.g., [4,5,6,7,0,1,2] is [0,1,2,4,5,6,7] rotated at index 4). Given a target, find its index in O(log n) time. All values are distinct.

Why is this asked in interviews?

This is asked at virtually every major company — Apple, Uber, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, Adobe, and many more — because it extends binary search to a non-standard sorted structure. It is a classic example of "modified binary search" where the sorted property is partially broken and candidates must identify which half is still sorted before deciding which direction to search.

Algorithmic pattern used

The pattern is modified binary search with half-sorted-half identification. At each step, compute mid. Identify which half is sorted: if nums[left] <= nums[mid], the left half is sorted. Check if target falls in the sorted range [nums[left], nums[mid]). If yes, narrow to left half; otherwise search right. If the right half is sorted (nums[mid] <= nums[right]), apply the same logic for [nums[mid], nums[right]].

Example explanation

Array: [6, 7, 0, 1, 2, 4, 5], target = 0.

• left=0, right=6. mid=3. nums[mid]=1. nums[left]=6 > nums[mid]=1 → right half [mid..right] is sorted: [1,2,4,5].
• 0 not in [1,5] → search left half. right=2.
• left=0, right=2. mid=1. nums[1]=7. nums[0]=6 ≤ 7 → left half sorted: [6,7].
• 0 not in [6,7] → search right half. left=2.
• left=right=2. nums[2]=0 = target → return 2.

Common mistakes candidates make

• Using nums[left] < nums[mid] (strict) instead of <=, causing incorrect behavior when left == mid.
• Not handling the rotation point correctly — always check which half is sorted before deciding direction.
• Using a three-part split (before pivot, at pivot, after pivot) which is more complex than necessary.
• Off-by-one errors in the boundary conditions — practice until the <= vs < boundaries feel natural.

Interview preparation tip

For the Search in Rotated Sorted Array coding problem, the binary search array interview pattern with rotation handling is the key. The single insight to memorize: at each step, one half is always sorted. Use this to decide which half contains the target. Interviewers at Grammarly and Anduril test edge cases: what if target is at the pivot? What if the array has 1 or 2 elements? Practice these explicitly.