Binary Search in Rotated Arrays

Hello! In our last few lessons, we've built a solid foundation in binary search, moving from finding exact values to locating boundaries with lower-bound and upper-bound searches. The common thread was that our binarySearch template relied on a fundamental property: the entire array was sorted.

Today, we're going to tackle a classic interview problem that challenges this assumption: searching in a rotated sorted array. Imagine an array like [0, 1, 2, 4, 5, 6, 7] that gets "rotated" to become [4, 5, 6, 7, 0, 1, 2]. It's no longer fully sorted, so our standard binary search won't work. Your goal for this lesson is to learn how to adapt binary search to solve this problem efficiently, specifically by learning to identify which half of the array remains ordered at each step.

The Problem with Rotation

A standard binary search works by comparing the target to the middle element and confidently eliminating one half of the array. For example, in a sorted array, if target < nums[mid], we know the target must be in the left half.

But in a rotated array like [4, 5, 6, 7, 0, 1, 2], this logic breaks. If our target is 0 and we pick a middle element 7 (at index 3), 0 < 7. A standard binary search would incorrectly discard the right half, where the 0 actually is.

So, how do we solve this in O(log n) time? We can't do a linear scan, as that would be too slow for typical interview constraints. The solution lies in a brilliant insight about the structure of a rotated array.

The Key Insight: One Half is Always Sorted

Even though the entire array isn't sorted, if you split it at any middle point, at least one of the two halves will be perfectly sorted.

• Consider [4, 5, 6, 7, 0, 1, 2]. Let's say mid is at index 3 (value = 7).
  • The left half is [4, 5, 6, 7]. This is sorted.
  • The right half is [0, 1, 2]. This is also sorted.
• Let's take a different mid. If mid is at index 5 (value = 1).
  • The left half is [4, 5, 6, 7, 0, 1]. This is not sorted.
  • The right half is [2]. This is (trivially) sorted.

This property is our foothold. If we can identify the sorted half, we can determine with certainty whether our target lies within its bounds. If it does, we search that half. If it doesn't, we know it must be in the other, unsorted half. In either case, we discard half the search space, preserving our O(log n) efficiency.

The following video from the "take U forward" channel provides an excellent explanation of why standard binary search fails and introduces this core idea of identifying the sorted half.

The Algorithm: A Modified Binary Search

Now that we have the core idea, let's formalize it into an algorithm. At each step of our binary search loop:

1. Calculate mid.

2. If nums[mid] equals our target, we're done. Return mid.

3. Identify the sorted half. We can do this with a simple comparison: if (nums[left] <= nums[mid]).

   • If this is true, the left half ([left...mid]) is sorted.
   • If false, the pivot point is somewhere in the left half, which means the right half ([mid...right]) must be sorted.

4. Decide where to search next.

   • Case 1: Left half is sorted (nums[left] <= nums[mid]).

     • We ask: Is our target in the range of this sorted half? That is, nums[left] <= target < nums[mid].
     • If YES: The target is in the left half. Discard the right: right = mid - 1.
     • If NO: The target must be in the other (unsorted) half. Discard the left: left = mid + 1.

   • Case 2: Right half is sorted (nums[left] > nums[mid]).

     • We ask: Is our target in the range of this sorted half? That is, nums[mid] < target <= nums[right].
     • If YES: The target is in the right half. Discard the left: left = mid + 1.
     • If NO: The target must be in the other (unsorted) half. Discard the right: right = mid - 1.

This logic guarantees that we correctly narrow down the search space at every step. This image provides a great visual for the first step of this logic.

The AlgoMonster article on this problem provides a very clear, step-by-step breakdown of this approach.

Example Walkthrough and Implementation

Let's trace the algorithm with the example from the article: nums = [4, 5, 6, 7, 0, 1, 2], target = 0.

• Initial: left = 0, right = 6.
• Iteration 1:
  • mid = 3, nums[mid] = 7. Not the target.
  • Is the left half sorted? nums[0] <= nums[3] (i.e., 4 <= 7)? Yes.
  • Is target in the sorted left half? nums[0] <= target < nums[3] (i.e., 4 <= 0 < 7)? No.
  • Search right: left = mid + 1 = 4.
• Iteration 2:
  • left = 4, right = 6.
  • mid = 5, nums[mid] = 1. Not the target.
  • Is the left half sorted? nums[4] <= nums[5] (i.e., 0 <= 1)? Yes.
  • Is target in the sorted left half? nums[4] <= target < nums[5] (i.e., 0 <= 0 < 1)? Yes.
  • Search left: right = mid - 1 = 4.
• Iteration 3:
  • left = 4, right = 4.
  • mid = 4, nums[mid] = 0. This is the target! Return mid, which is 4.

The NeetCode video below provides another excellent visualization of this process, which can help solidify your understanding.

Here is the TypeScript implementation that directly follows our algorithm.

function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);

        if (nums[mid] === target) {
            return mid;
        }

        // Case 1: The left half [left...mid] is sorted.
        if (nums[left] <= nums[mid]) {
            // Check if target is in the sorted left half.
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                // Target must be in the right half.
                left = mid + 1;
            }
        } 
        // Case 2: The right half [mid...right] is sorted.
        else {
            // Check if target is in the sorted right half.
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                // Target must be in the left half.
                right = mid - 1;
            }
        }
    }

    return -1; // Target not found
}

Common Pitfalls

This problem is notorious for off-by-one errors and tricky boundary conditions. Given your expressed "algo phobia," being aware of these traps is half the battle. The AlgoMonster resource has an excellent section on this.

Conclusion

In this lesson, you've learned how to adapt the powerful binary search algorithm to a non-obvious case: a rotated sorted array. By staying calm and reasoning about the structure of the data, you can find an invariant—that one half is always sorted—and exploit it to maintain O(log n) performance.

Here are the key takeaways:

• A rotated sorted array can be searched in O(log n) time by modifying binary search.
• The core insight is that for any mid point, either the left subarray (nums[left...mid]) or the right subarray (nums[mid...right]) is guaranteed to be sorted.
• You can identify the sorted half by checking if nums[left] <= nums[mid].
• Once the sorted half is identified, you check if the target lies within its range. If it does, you search that half; otherwise, you search the other half.

In our next lesson, we will continue this theme of searching in partially ordered data structures. We'll move from a 1D array to a 2D matrix that is sorted by row and column, and you'll learn another clever elimination strategy to find an element efficiently.