Rotated Sorted Search

Searching in a rotated sorted array involves finding a target element within an array that was originally sorted but has been shifted by some number of positions. While a linear scan would work, a more efficient approach leverages the fact that at least one half of the array will always remain sorted, allowing for a modified binary search with logarithmic time complexity.

Initializing Pointers

We begin by establishing two pointers, `l` (left) and `r` (right), at the beginning and end of the array, respectively. These pointers define our current search space. We continue our search as long as `l` is less than or equal to `r`.

Finding the Midpoint

In each iteration, we calculate the midpoint `m` using integer division `(l + r) // 2`. We then compare the value at `nums[m]` with our `target`.

Determining the Sorted Half

The core of the algorithm lies in identifying which half of the array (from `l` to `m`, or from `m` to `r`) is currently sorted. We check if `nums[l] <= nums[m]`. If this condition is true, the left half (`nums[l]` to `nums[m]`) is sorted. Otherwise, the right half (`nums[m]` to `nums[r]`) must be sorted.

Narrowing the Search Space

Once the sorted half is identified, we determine if the `target` falls within the range of that sorted half. If it does, we narrow our search to that half by adjusting `l` or `r` accordingly. If the `target` is not in the sorted half, it must be in the unsorted half, and we adjust our pointers to search there instead. This process effectively halves the search space in each step.

Pseudocode

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target: return m
        if nums[l] <= nums[m]: # Left half is sorted
            if nums[l] <= target < nums[m]: r = m - 1
            else: l = m + 1
        else: # Right half is sorted
            if nums[m] < target <= nums[r]: l = m + 1
            else: r = m - 1
    return -1

Key Takeaways

• A rotated sorted array can be searched efficiently using a modified binary search.
• At least one half of the array will always be sorted, enabling logarithmic time complexity.
• The algorithm involves identifying the sorted half and checking if the target lies within its range.
• Pointers `l` and `r` are adjusted to continuously narrow the search space.
• The search concludes when the target is found or the search space is exhausted.