Search in Rotated Sorted Array

The machine must find a target in an array that was sorted, then rotated at an unknown pivot — values are distinct. A normal binary search fails because the array is not monotonic, but at any midpoint one of the two halves is fully sorted. The trick: detect which half is sorted, check whether the target lies inside its range, and narrow into the half that must contain the target.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:          # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                              # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Steps: (1) find the sorted half via nums[lo] <= nums[mid], (2) test membership in that half, (3) narrow accordingly. Each iteration still discards half the window, so the log bound holds.

Time is O(log n). Space is O(1).

Trickiest edge case: a fully rotated array — [3,4,5,1,2] — where both range checks must be inclusive on exactly one end. The <= in the sorted-half test is deliberate: when lo == mid, the left half is a single element. Distinct values are guaranteed, so there is no duplicate ambiguity.