Search in Rotated Sorted Array

Learning goal: Recognize why a rotated sorted array still supports logarithmic search.

Core idea A rotation moves a sorted prefix behind a sorted suffix, so the entire array may no longer be monotonic. However, for any chosen midpoint, at least one side of the midpoint is guaranteed to remain sorted. That local structure is enough to discard half of the remaining search interval.

Algorithm plan

• Set lo = 0 and hi = n - 1.
• Compute mid while lo <= hi.
• Identify the sorted half using nums[lo] <= nums[mid].
• Check whether the target lies within that half's endpoint range.
• Keep that half when it can contain the target; otherwise keep the opposite half.

Micro-example For [4,5,6,7,0,1,2], midpoint value 7 makes [4,5,6,7] visibly sorted. Since 0 is not between 4 and 7, the answer must be to the right.

Pitfalls

• Do not assume the whole array is monotonic.
• Use inclusive comparisons at the sorted half's endpoints.
• Use lo <= hi so a one-element interval is checked.

Recap

• Rotation breaks global order, not every local half.
• The sorted half tells us which direction is safe.
• Each decision removes at least half the interval.

Learning goal: Determine which half is sorted and use its value range to guide the search.

Core idea Compare nums[lo] with nums[mid]. If nums[lo] <= nums[mid], the left half is sorted; otherwise, the right half must be sorted. Once that half is known, its endpoints describe an ordinary sorted interval, so a target-range test tells us whether to search inside it.

Decision table

Micro-example At lo = 0, mid = 3, hi = 6, values are 4, 7, 2. The left side is sorted, but target 0 is not in [4,7), so discard it.

Pitfalls

• The sorted-side test comes before the target-range test.
• The inequalities differ slightly because mid is already inspected.
• “Target is smaller” alone is not enough to choose left after rotation.

Recap

• nums[lo] <= nums[mid] identifies a sorted left half.
• Range membership decides whether that half can contain the target.
• The other case is symmetric for the right half.

Learning goal: Translate the sorted-half idea into a constant-space binary-search algorithm.

Core idea The loop maintains a simple invariant: if the target exists, it is inside the inclusive interval [lo, hi]. At each midpoint, either the left or right half is sorted. If the target lies inside that sorted half's value range, discard the opposite half; otherwise discard the sorted half. Because mid is checked first, the remaining interval always shrinks.

Algorithm plan

lo = 0, hi = n - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] == target: return mid
    if nums[lo] <= nums[mid]:
        if nums[lo] <= target < nums[mid]: hi = mid - 1
        else: lo = mid + 1
    else:
        if nums[mid] < target <= nums[hi]: lo = mid + 1
        else: hi = mid - 1
return -1

Micro-example For target 0, the first midpoint is index 3 with value 7. The left half is sorted, but 0 is outside its range, so lo jumps to 4; the interval is cut from seven positions to three.

Pitfalls

• Check equality at mid before changing boundaries.
• Use mid + 1 and mid - 1 to avoid repeating a midpoint.
• With distinct values, nums[lo] <= nums[mid] cleanly identifies the left-sorted case.

Recap

• Maintain target containment in [lo, hi].
• Identify order first, then test range membership.
• Every iteration halves the candidates, giving O(log n) time.

Learning goal: Trace every boundary update on one complete example.

Core idea We will search nums = [4,5,6,7,0,1,2] for target = 0. The important question is not simply whether the target is smaller than nums[mid]; it is whether the target fits the sorted half identified at that step.

Trace

Micro-example After step 1, the surviving interval is [0,1,2] at indices 4..6. At step 2, the sorted left half has values [0,1], so target 0 must be there; checking index 4 finishes the search.

Pitfalls

• Do not move hi merely because target is less than nums[mid].
• Record the sorted half using the current boundaries, not the original array ends.
• A one-element interval still requires an equality check.

Recap

• The example takes three midpoint checks.
• The rotation changes which half is sorted, not the halving process.
• The final answer is index 4.

Learning goal: Avoid the boundary mistakes that make rotated binary search incorrect.

Core idea The most common error is treating the rotated array as if its global order were intact. A comparison such as target < nums[mid] does not by itself reveal which boundary to move, because the pivot may lie between mid and the target. First classify the sorted half, then use that half's range.

Edge-case checklist

• No rotation: The left half is sorted at every step, so the algorithm behaves like ordinary binary search.
• Rotation at an endpoint: The array may look fully sorted; the same logic still works.
• Target at lo or hi: Inclusive endpoint checks must preserve those candidates.
• One element: The loop checks lo == hi before terminating.
• Absent target: Boundaries cross only after every viable interval has been eliminated.

Micro-example At [4,5,6,7,0,1,2] with midpoint 7, target 0 is smaller than 7. That fact alone is misleading: the correct move is right, because the sorted left range is [4,7] and cannot contain 0.

Pitfalls

• Forgetting < versus <= at the correct endpoint.
• Leaving mid inside the interval after rejecting it.
• Confusing “sorted half” with “half containing the target.”

Recap

• Global monotonicity is false after rotation.
• Local sortedness is sufficient.
• Boundary updates must make strict progress.

Learning goal: Justify the efficiency of the algorithm and retain its reusable pattern.

Core idea Each iteration performs a constant number of comparisons and discards one half of the active interval. The rotation changes the classification work, but it never changes the amount removed. The algorithm stores only three indices, so its auxiliary space remains constant.

Complexity

Reusable pattern

while the interval is nonempty:
    inspect midpoint
    identify a sorted half
    test target membership in that half
    discard the impossible half

Micro-example Seven candidates become three, then one, then a result. No auxiliary array is created, and no linear scan is needed.

Pitfalls

• Calling the solution O(n) because the array is rotated.
• Using extra storage to “unrotate” the array, which is unnecessary.
• Forgetting that the binary-search proof depends on distinct values here.

Recap

• Time: O(log n).
• Space: O(1).
• Rotation does not defeat binary search when one sorted half is identified first.