Search for a target in a rotated sorted array in O(log n).

How to think about it

The O(log n) requirement is the interviewer telling you, without saying it, that a linear scan is off the table — they want binary search, and they want to see how you adapt it when the array has been rotated at an unknown pivot. The instinct to pick a midpoint is right; the twist is that you cannot blindly compare the target to nums[mid] and pick a side, because the half containing the pivot is not sorted.

The unlock is a small invariant: cut anywhere, and at least one of the two halves is cleanly sorted with no pivot running through it. You can tell which by comparing nums[lo] to nums[mid]. If nums[lo] <= nums[mid], the left half is the sorted one; check whether the target lies inside [nums[lo], nums[mid]) and search left if so, otherwise right. If not, the right half is sorted; check whether the target lies inside (nums[mid], nums[hi]] and search right if so, otherwise left. Either way you discard half the array each step, so the rotation costs you only one extra comparison and the O(log n) guarantee holds.

A worked example

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 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

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # target past the pivot
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # absent value
print(search_rotated([1], 0))                      # single element, miss
print(search_rotated([1], 1))                      # single element, hit
print(search_rotated([3, 1], 1))                   # rotation at the first index

4
-1
-1
0
1

Follow the first call on [4, 5, 6, 7, 0, 1, 2] for target 0. At mid=3 the value is 7; since nums[0]=4 <= 7, the left half [4..7] is sorted, and 0 is not inside it, so we jump right. At mid=5 the value is 1; now nums[4]=0 <= 1, so that half [0..1] is sorted, 0 falls in it, and we narrow left until mid=4 lands on 0 — index 4. The two [1] cases show the loop’s boundaries: it returns 0 on a hit and -1 on a miss without ever indexing out of range.