Modified Binary Search for Rotated Sorted Arrays

1. Understanding the Rotated Sorted Array

A rotated sorted array is an array that was originally sorted in ascending order but was then "rotated" at some unknown pivot point. This means a suffix of the array was cut and moved to the beginning.

For example, if we start with the sorted array:
[0, 1, 2, 4, 5, 6, 7]

A rotation at the element 4 (index 3) would result in:
[4, 5, 6, 7, 0, 1, 2]

The array is no longer fully sorted, but it retains a crucial structure: it's composed of two individually sorted segments. A linear scan would find an element in $O(n)$ time, but the interview constraint is almost always $O(\log n)$, which strongly hints at a modified binary search.

To get a clear visual intuition for this structure, let's start with a short video.

2. The Core Insight: One Half is Always Sorted

The key to solving this problem in $O(\log n)$ time is realizing a fundamental property of rotated sorted arrays:

When you split a rotated sorted array at its midpoint, at least one of the two halves (left or right) will be perfectly sorted.

This single property allows us to adapt binary search. In each step, we can identify which half is sorted and then make an intelligent decision about where the target must lie.

Our algorithm will look like this at each step:

1. Calculate the middle index mid.
2. If nums[mid] is the target, we've found it. Return mid.
3. Determine which half is sorted. A simple way to check is if nums[left] <= nums[mid]. If this is true, the left half is sorted. Otherwise, the right half must be sorted.
4. Once the sorted half is identified, check if the target value falls within the range of that sorted half.
   • If it does, we can confidently discard the other half and continue our search in the sorted portion.
   • If it doesn't, the target must be in the other (unsorted) half, so we discard the sorted half and search there.

3. Developing the Algorithm

Let's refine the logic from the previous section. We'll use l and r for our left and right pointers.

while l <= r:
    mid = l + (r - l) // 2

    if nums[mid] == target:
        return mid

    # Case 1: The left half (from l to mid) is sorted
    if nums[l] <= nums[mid]:
        # Is the target in this sorted left half?
        if nums[l] <= target < nums[mid]:
            r = mid - 1  # Search left
        else:
            l = mid + 1  # Search right (the unsorted part)
            
    # Case 2: The right half (from mid to r) is sorted
    else:
        # Is the target in this sorted right half?
        if nums[mid] < target <= nums[r]:
            l = mid + 1  # Search right
        else:
            r = mid - 1  # Search left (the unsorted part)

return -1 # Target not found

To see this logic explained and applied step-by-step, let's return to the NeetCode video.

For a different perspective and a very detailed textual walkthrough, the following resource is also excellent.

4. Extending the Pattern: Find Minimum Element

The core idea of identifying the sorted portion of a rotated array is a powerful pattern. It can be used to solve other related problems, like Find Minimum in Rotated Sorted Array (LeetCode 153).

The logic is similar:

• Perform a binary search.
• In each step, check if the middle element is in the "larger" left sorted portion or the "smaller" right sorted portion.
• If nums[mid] is greater than or equal to nums[left], it means mid is in the left (larger values) sorted portion. Therefore, the true minimum must be to its right. So, we search right: left = mid + 1.
• Otherwise, mid is in the right (smaller values) sorted portion. The minimum could be nums[mid] itself or an element to its left. So, we search left: right = mid - 1.

Watching a solution for this problem can help solidify the general pattern.

Conclusion

You have now learned a powerful and frequently tested binary search pattern. By understanding the underlying structure of a rotated sorted array, you can adapt the standard algorithm to solve the problem efficiently.

Key Takeaways:

• A rotated sorted array consists of two sorted subarrays.
• The key insight for an $O(\log n)$ solution is that at any midpoint, at least one half of the array is guaranteed to be sorted.
• The algorithm involves identifying the sorted half and then checking if the target lies within its range to decide which half to discard.
• This pattern of identifying a sorted subsection is versatile and can be applied to related problems like finding the minimum element.

In our next lesson, we will explore a completely different application of binary search. Instead of searching for an element within a data structure, we will learn how to search for an optimal value in a range of possible answers, a technique known as "Binary Search on the Answer Space."