Search in Rotated Sorted Array

Rotation breaks global order, not all order. Find the sorted half, test its value range, and discard what that range proves impossible.

Read the problem contract

You receive an ascending array of distinct integers that may have been rotated at an unknown index. Return the target’s index in the post-rotation array, or -1 when the target is absent.

For example:

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
answer = 4

The answer is 4 because that is where 0 appears after rotation. You are not returning the pivot, and you are not translating the index back to the original sorted array.

The constraints establish the important algorithmic contract:

• Values are distinct.
• The original array was sorted in ascending order.
• Rotation may be absent or may occur at an unknown index.
• The required runtime is O(log n).

A linear scan is easy:

for index, value in enumerate(nums):
    if value == target:
        return index
return -1

But that inspects every element in the worst case. The logarithmic requirement tells us to preserve binary search’s central behavior: eliminate a large portion of the candidate interval after each midpoint inspection.

The rotation means the entire interval is no longer sorted. That is the obstacle. It is also the clue.

Diagnose the broken binary-search model

Ordinary binary search depends on one global fact: the whole candidate interval is sorted. After rotation, an array such as

[4, 5, 6, 7, 0, 1, 2]

contains two increasing runs:

[4, 5, 6, 7] and [0, 1, 2]

The pivot creates a drop from 7 to 0, so comparing only target with nums[mid] is no longer enough. The midpoint value tells you very little until you know which side retains sorted order.

Here is the stronger mental model:

At every midpoint, at least one half of the current interval is sorted.

That statement remains true even when the current interval crosses the rotation point. With distinct values, the comparison between the left endpoint and the midpoint identifies the sorted side:

nums[left] <= nums[mid]

If this is true, the left half is sorted. Otherwise, the right half is sorted.

The sorted half is our measurement surface. Its endpoints define a complete value range. If the target falls outside that range, the target cannot be hiding somewhere inside the sorted half. We can throw that half away with proof rather than hope.

This is modified binary search: the loop still shrinks an interval around a possible answer, but it first reconstructs enough local order to decide which interval to keep.

Derive the elimination rule

Use an inclusive candidate interval:

[left, right]

The invariant will be:

If the target exists, its index is somewhere inside [left, right].

At each iteration:

1. Compute mid.
2. Return mid immediately if nums[mid] == target.
3. Identify which half is sorted.
4. Check whether the target’s value could lie inside that sorted half.
5. Keep the possible half and discard the other.

The equality check must happen first. Once we know that nums[mid] is the target, we are done. This also lets the later range checks exclude mid safely.

Case 1: the left half is sorted

The condition is:

nums[left] <= nums[mid]

The sorted left half is:

[left, mid]

Because its values are ordered, the target can be inside it only when:

nums[left] <= target < nums[mid]

The left endpoint is inclusive because nums[left] may be the target. The midpoint is exclusive because we already checked it.

If the condition is true, discard everything from mid onward:

right = mid - 1

Otherwise, the target cannot be in the sorted left half, so search the other side:

left = mid + 1

Case 2: the right half is sorted

If the left half is not sorted, then the right half is sorted under the distinct-value contract.

The sorted right half is:

[mid, right]

Since mid was already checked, the target can remain there only when:

nums[mid] < target <= nums[right]

The right endpoint is inclusive because nums[right] may be the target. Again, mid is excluded because equality was handled first.

If the target lies in that range, discard the left side:

left = mid + 1

Otherwise, discard the right side:

right = mid - 1

The complete decision structure is therefore:

check nums[mid]
identify sorted half
check target against that half's value range
discard the impossible half

Do not memorize the inequalities as isolated syntax. Derive them from the interval you are keeping. The sorted half gives you two ordered boundaries; the target either fits between them or it does not.

Prove the invariant and logarithmic progress

The sorted half invariant is the central correctness argument:

If target exists in the array, it remains inside the current inclusive interval [left, right].

Initially, the interval is the entire array, so the invariant is true.

Now assume the invariant is true at the start of an iteration.

Why discarding the sorted half is safe

Suppose the left half is sorted:

nums[left] <= nums[mid]

If the target satisfies:

nums[left] <= target < nums[mid]

then it may be in the left half, so we keep [left, mid - 1] after checking mid.

If the target does not satisfy that range, it cannot occur inside the sorted left half:

• If target < nums[left], it is below every value in that half.
• If target >= nums[mid], it is at or above the midpoint, which was already checked for equality.

So the target, if present, must be in the other half. Setting:

left = mid + 1

preserves the invariant.

The right-sorted case is symmetric. If:

nums[mid] < target <= nums[right]

the target may be in the right half, so retain it. Otherwise, ordered values prove that it cannot be there, and we set:

right = mid - 1

In every branch, mid has already been checked and the next interval excludes it. The interval therefore shrinks strictly.

Because each update removes roughly half of the current candidates, the loop performs O(log n) iterations. The algorithm stores only left, right, and mid, so its extra space is O(1).

An already sorted array needs no special case. For every interval, the left half will be recognized as sorted, and the same range test will decide whether to search left or right. Special cases are useful only when the general rule cannot handle the situation. Here, it can.

Duplicates change the proof. If nums[left] == nums[mid], the comparison may not tell us which side is meaningfully sorted. This article relies on distinct values; duplicate-sensitive search needs additional logic and may not preserve the same elimination guarantee.

Dry-run: present and absent targets

Use:

nums = [4, 5, 6, 7, 0, 1, 2]

Target 0

At the first midpoint, the left half is sorted, but 0 is below its lower boundary, 4. That eliminates indices 0 through 3.

At the second midpoint, the right half is sorted. The target is smaller than its lower boundary, 1, so the search moves left.

The returned index is 4, the index in the rotated array.

Target 3

The first midpoint is still index 3, with value 7. The left half is sorted, but:

4 <= 3 < 7

is false, so search [4, 6].

At mid = 5, the right half [1, 2] is sorted. The target does not satisfy:

1 < 3 <= 2

so search [4, 4].

At index 4, the value is 0. The one-element interval is not the target, and the update produces:

right = mid - 1

so the interval becomes empty. The loop ends and returns -1.

That final empty interval is not an error. It is the proof’s conclusion: every candidate has been eliminated.

Implement the Python solution

Here is the complete rotated array Python implementation:

def search(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2

        # Check the midpoint before excluding it from future intervals.
        if nums[mid] == target:
            return mid

        # The left half is sorted.
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1

        # The right half is sorted.
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Each variable has a direct obligation:

• left and right define the inclusive candidate interval.
• mid is the next value to inspect.
• The sorted-half comparison determines which value range can be trusted.
• The range test decides which half can still contain the target.
• mid - 1 and mid + 1 guarantee progress after mid has been checked.

I prefer this single-pass form over first finding the pivot and then running ordinary binary search. A separate pivot search can work, but it creates another boundary contract and another place for off-by-one errors. The single loop identifies the useful sorted region exactly when it needs it.

Common implementation failures

Applying ordinary binary-search comparisons.

A check such as target < nums[mid] does not tell you which pointer to move when the interval is rotated. You must first classify a sorted half.

Forgetting the already sorted interval.

When the current interval does not cross the pivot, the left half still satisfies:

nums[left] <= nums[mid]

That is expected. Do not treat it as a special failure state.

Using the wrong endpoint inclusivity.

For a sorted left half, use:

nums[left] <= target < nums[mid]

For a sorted right half, use:

nums[mid] < target <= nums[right]

The outer endpoint may contain the target. The midpoint has already been checked.

Moving a pointer to mid.

Updates such as left = mid or right = mid can stall when only one or two elements remain. Once equality has failed, remove mid:

left = mid + 1
right = mid - 1

Adding duplicate-handling logic to the wrong contract.

The distinct-value assumption is doing real work here. Do not quietly mix in rules for a different problem and then claim the same proof.

Complexity and edge-case checks

The time complexity is O(log n) because each iteration discards one half of the current candidate interval. The extra space is O(1) because the algorithm uses only a fixed number of integer variables.

Test the boundaries deliberately. The branch conditions are short; the mistakes hide at the edges.

The stated problem contract uses a non-empty array, but the same loop also handles an empty input: right becomes -1, left <= right is false, and the function returns -1 without indexing the array.

Before submitting, verify four things:

1. Equality is checked before range classification.
2. Exactly one half is identified as sorted.
3. The target-range test uses the correct inclusive and exclusive boundaries.
4. Every pointer update moves beyond mid.

The transferable pattern

When rotation breaks global order, do not abandon binary search immediately. Ask a narrower question:

Which local region is still ordered enough to eliminate candidates?

At a midpoint in this problem, one half remains trustworthy. Classify it. Use its endpoint values as a range proof. Discard only what that proof makes impossible.

That is the reusable move behind this modified binary search:

Recover local order. Measure the target against it. Shrink the interval strictly.

Once that sequence becomes automatic, the array stops looking like a broken sorted structure and starts looking like a binary-search problem with one damaged seam.