Searching a Rotated Sorted Array

The array was sorted and then rotated, so it consists of two sorted runs with a break somewhere in the middle. At each step of a binary search you can determine which half is sorted by comparing the first element of the interval with the midpoint. Once you know which half is in order, you can decide whether the target lies inside it, and you keep only that half.

The step by step reasoning is: if the midpoint equals the target, you are done. Otherwise, check whether the left half is sorted, which it is when the value at low is less than or equal to the value at mid. If it is sorted, the target either falls inside that half, in which case you narrow to it, or it falls beyond it, in which case you narrow to the other half. If the left half is the broken one, then the right half is sorted, and you apply the mirrored test.

The mechanism is that the sorted half behaves like an ordinary sorted array, so the standard comparison test applies inside it. That is what preserves the halving. A linear search through the whole array would also find the answer, but it throws away the structure that makes the problem interesting.

The trade-off to name is that the rotated version costs logarithmic time and constant space, while the brute force costs linear time and no extra space. The complication worth raising is duplicates. If the interval endpoints are equal you cannot tell which half is sorted, and the standard fix is to shrink one end, which makes the worst case quadratic for arrays made entirely of one repeated value. Interviewers often follow up with exactly that case, so it is worth having the answer ready.

At every step, identify which half of the current interval is sorted, then check whether the target falls inside that half before narrowing to it.

def search_rotated(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if values[low] <= values[mid]:
            if values[low] <= target < values[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:
            if values[mid] < target <= values[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1


data = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(data, 0))
print(search_rotated(data, 3))

The outputs are 4 and minus one. The zero is at index four, and the 3 is not present anywhere in the array, so the search exhausts the interval.

The mechanism is the sorted half test. When the value at low is less than or equal to the value at mid, the left half has not been broken by the rotation and is therefore sorted, so a range check against it is valid. Otherwise the right half is the sorted one, and the same range check applies to it with the inequalities reversed.

The trade-off to name is that every iteration discards half of the interval, so the bound is logarithmic even though the array is not sorted overall. The price is that the logic is noticeably more involved than a plain binary search, and a single comparison written the wrong way silently returns minus one for a value that is present. Writing the two branches out separately, as above, is what keeps it readable. Mentioning that the same trick works for finding the pivot index, and then running two ordinary binary searches, is a good alternative to propose in an interview.

Use the membership test and the index method. Python checks the whole list, and if the value is there, index returns where it first appeared. That is a linear scan with a small constant, and it is completely correct regardless of how the array was rotated.

def search_rotated_linear(values, target):
    if target in values:
        return values.index(target)
    return -1


data = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated_linear(data, 0))
print(search_rotated_linear(data, 3))

The outputs are 4 and minus one, matching the logarithmic version exactly. The rotation does not change which elements exist or where they sit, it only changes the order, so a straightforward search works.

The mechanism is that the two operations together are a single scan. The membership test walks the list until it finds the value or reaches the end, and the index call then walks it again to locate the position. That is two passes rather than one, which is worth noticing because it means the simple version is closer to twice the cost of a hand-written single-pass loop.

The trade-off to name is the asymptotics. The linear version is O of n time and O of 1 space, with no precondition beyond the value being present or absent, while the logarithmic version is O of log n but only works because the array has a very specific structure. For a one-off lookup on a small array, the simple version is the right choice. For repeated lookups or a very large array, building a dictionary of values to indices once and then answering each lookup in constant time is usually better than either.