116. Search Rotated Sorted Array

Why this mechanism works

Rotation breaks global sortedness but introduces at most one descending break. Around a midpoint, at least one side is still normally sorted. Identify that trustworthy side, test whether target lies within its value range, and keep either it or the opposite side. Do not launch a separate binary search inside that side. The local sortedness fact is used only to justify one safe exclusion in the current search.

State and boundaries

[left,right) contains every remaining candidate. right-1 is the last candidate index. Equality at mid is checked before strict range tests exclude it.

Protocol

1. Compute mid inside the nonempty candidate interval.
2. Return immediately on equality.
3. If nums[left]<=nums[mid], the left side is sorted.
4. Keep it only when nums[left]<=target<nums[mid].
5. Otherwise the right side is sorted: keep it only when nums[mid]<target<=nums[right-1].
6. Use right=mid or left=mid+1 to discard the rejected midpoint.
7. Return -1 if the interval empties.

Visualization

values: 15 18 20 | 1 3 5 8 9 13
index:   0  1  2   3 4 5 6 7  8
left=0, mid=4, right=9 (boundary after 13)
15>3 -> right side [3,5,8,9,13] is sorted

Complete boundary walkthroughs

Why one side remains trustworthy

Think of the array as two increasing blocks: [15,18,20] followed by [1,3,5,8,9,13]. There is only one descending edge, 20 to 1. Two overlapping midpoint sides cannot both contain that one edge in their interiors. Distinct values make their endpoints reveal which side is ordered. A later candidate interval may contain the break or lie entirely inside one increasing block; the same test still applies.

Complete trace for target 5

Iteration 1: [left,right)=[0,9), mid=4, value=3. Since 15>3, the right side is sorted. The test 3<5<=13 is true, so discard the checked midpoint and keep [5,9).

Iteration 2: [5,9), mid=7, value=9. Now 5<=9, so the left side is sorted. The test 5<=5<9 is true. Set right=7, leaving [5,7).

Iteration 3: [5,7), mid=6, value=8. The left side is sorted and 5<=5<8 is true. Set right=6, leaving [5,6).

Iteration 4: [5,6), mid=5, value=5. Equality succeeds and returns index 5. The exclusive right boundary is 6; it is not a value to read.

Complete trace for target 18

Iteration 1: [0,9), mid=4, value=3. The right side is sorted, but 3<18<=13 is false. If 18 exists, it must be in the other side. Set right=4, preserving [0,4), whose values are [15,18,20,1]. It is safe to keep a rotated-looking side; it need not already be sorted as a whole.

Iteration 2: [0,4), mid=2, value=20. The left side [15,18,20] is sorted and 15<=18<20 is true. Set right=2, leaving [0,2).

Iteration 3: [0,2), mid=1, value=18. Return index 1.

Why the two updates are asymmetric

After rejecting mid, the candidates on its left occupy [left,mid). Assigning right=mid retains exactly that interval because right is excluded. Candidates on its right occupy [mid+1,right), so left must become mid+1. With left=3,right=4,mid=3, assigning left=mid changes nothing and cannot prove progress.

Why this is not one global first-true search

The comparison nums[i]>=target can change truth more than once across a rotation. This exact search relies on a local sorted-half argument instead of pretending that global predicate is monotone. The next kata shows a different task where a carefully chosen predicate relative to the fixed final value does become monotone.

Python implementation

def search_rotated(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right - 1]:
                left = mid + 1
            else:
                right = mid
    return -1

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 search_rotated: left, right = 0, len(nums)
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=5; left=0; right=9

L4 search_rotated: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=5; left=0; right=9; mid=4

L14 search_rotated: left = mid + 1
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=5; left=5; right=9; mid=4

L4 search_rotated: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=5; left=5; right=9; mid=7

L9 search_rotated: right = mid
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=5; left=5; right=7; mid=7

L4 search_rotated: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=5; left=5; right=7; mid=6

L9 search_rotated: right = mid
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=5; left=5; right=6; mid=6

L4 search_rotated: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=5; left=5; right=6; mid=5

L2 search_rotated: left, right = 0, len(nums)
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=18; left=0; right=9

L4 search_rotated: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=18; left=0; right=9; mid=4

L16 search_rotated: right = mid
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=18; left=0; right=4; mid=4

L4 search_rotated: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=18; left=0; right=4; mid=2

L9 search_rotated: right = mid
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=18; left=0; right=2; mid=2

L4 search_rotated: mid = (left + right) // 2
nums=[15, 18, 20, 1, 3, 5, 8, 9, ...]; target=18; left=0; right=2; mid=1

Why the solution is correct

With distinct values and one rotation break, nums[left]<=nums[mid] identifies a sorted left side; otherwise the right side must be sorted. A target outside the sorted side's endpoint range cannot occur there. A target inside that range cannot occur in the disjoint value block on the other side. Each branch therefore preserves a possible match while discarding mid, which was already checked. The interval strictly shrinks, so the search terminates.

Time and space

O(log(n+1)) time and O(1) auxiliary space. Distinctness is essential to this logarithmic sorted-half decision.

Common mistakes

left=mid can loop forever on one candidate. nums[right] is outside the interval. Duplicates can make nums[left]==nums[mid]==nums[right-1], hiding the rotation and invalidating this exact decision rule.

Reasoning card

Transfer exercise

Permit duplicates, construct an ambiguous equal-endpoint example, and explain why discarding one equal boundary can degrade the worst case to linear time.