DSA Searching a Rotated Sorted Array

The problem

Search in a Rotated Sorted Array finds the index of a target in a sorted list that was cut at one point and swapped in two parts. The answer is minus 1 when the target is absent.

The values are distinct in this article. The cut point is not given. An unrotated list is allowed, because a cut at the start changes nothing.

cases = [
    ([4, 5, 6, 7, 0, 1, 2], 0, 4),
    ([4, 5, 6, 7, 0, 1, 2], 5, 1),
    ([4, 5, 6, 7, 0, 1, 2], 3, -1),
    ([5, 1, 3], 3, 2),
    ([1, 2, 3], 2, 1),
]
for nums, target, expected in cases:
    print("nums", nums, "target", target, "index:", expected)

Read one row at a time. The first list is the sorted list 0 to 7 with its parts swapped. The last row shows the same search working on a list that was never rotated.

Intuition: plain binary search trusts the wrong half

The first idea runs ordinary binary search and trusts the whole range to be sorted. That trust is false after a rotation. One part of the range rises, then the values drop and rise again.

The trap shows on the target 0 below. Plain binary search compares 0 with the middle value 7 and moves left. The target sits on the right, so the search reports a miss for a value that is present.

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

nums = [4, 5, 6, 7, 0, 1, 2]
print("plain search for 0:", plain_search(nums, 0))
print("index of 0 by scanning:", nums.index(0))

The plain search answers minus 1 and the scan answers 4. The method failed, not the data. Any fix must ask which part of the range is sorted before trusting a comparison.

Brute force: scan every value

The brute force walks the list from the left and compares each value with the target. A counter records the comparisons. The first equal value gives its index, and a full walk with no equal value gives minus 1.

def search_brute(nums, target):
    checked = 0
    for i, value in enumerate(nums):
        checked += 1
        if value == target:
            return i, checked
    return -1, checked

nums = [4, 5, 6, 7, 0, 1, 2]
for target in [0, 5, 3]:
    index, checked = search_brute(nums, target)
    print("target", target, "index:", index, "comparisons:", checked)

The missing target pays the full list length. A present target pays for its position. Neither cost improves when the list grows, and the sorted origin of the list is wasted.

The optimal solution: test the sorted half

One half of the current range is always fully sorted, and a range test on that sorted half shows whether the target can sit inside it, so the search keeps that half or the other and halves the range. That one sentence is the whole method.

The left half is sorted when the left edge value is at or below the middle value. The right half is sorted otherwise. A target inside the sorted half's value range keeps that half, and any other target keeps the opposite half.

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

cases = [
    ([4, 5, 6, 7, 0, 1, 2], 0, 4),
    ([4, 5, 6, 7, 0, 1, 2], 5, 1),
    ([4, 5, 6, 7, 0, 1, 2], 3, -1),
    ([5, 1, 3], 3, 2),
    ([1, 2, 3], 2, 1),
]
for nums, target, expected in cases:
    result = search(nums, target)
    print("nums", nums, "target", target, "->", result, "expected:", expected, "match:", result == expected)

All five cases from the start of the article pass. The trap target 0 from the intuition section now lands at index 4. The absent target still answers minus 1.

Walkthrough: searching for 0

The walk searches the main list for 0. The state is the range, its middle value, and which half is sorted. Each step keeps one half and drops the other.

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
lo = 0
hi = len(nums) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    if nums[mid] == target:
        print("range", lo, hi, "- mid value", nums[mid], "- move: found at", mid)
        break
    if nums[lo] <= nums[mid]:
        side = "left half sorted"
        move = "left" if nums[lo] <= target < nums[mid] else "right"
    else:
        side = "right half sorted"
        move = "right" if nums[mid] < target <= nums[hi] else "left"
    print("range", lo, hi, "- mid value", nums[mid], "-", side, "- move:", move)
    if move == "left":
        hi = mid - 1
    else:
        lo = mid + 1

The first step trusts the sorted left half and rejects it, because 0 lies outside the range 4 to 7. The second step works on the range from index 4 to 6, whose left part runs 0 to 1 and can hold the target, so the search moves left. The third step lands on 0 itself.

Complexity

The scan compares up to n values, so its time is O(n). The rotated search halves its range on every step, so its time is O(log n).

Both methods store only a few index values. Their extra space is O(1).

def search_steps(nums, target):
    lo = 0
    hi = len(nums) - 1
    steps = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        steps += 1
        if nums[mid] == target:
            return steps
        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 steps

for n in [7, 15, 31]:
    base = list(range(n))
    cut = n // 2
    rotated = base[cut:] + base[:cut]
    print("values", n, "- scan worst case:", n, " rotated search steps for a missing target:", search_steps(rotated, n + 100))

Counts beat clocks here. At 31 values the scan can pay 31 comparisons. The rotated search empties its range in 5 steps.

Edge cases and pitfalls

Treating the whole range as sorted is the pitfall shown in the intuition section. The fix is the sorted-half test on every step, not only the first. A half that was mixed can become fully sorted after one cut, and the test notices.

Duplicates would break the sorted-half test, because equal edge and middle values can hide which side holds the drop. This article uses distinct values, as the problem section states. Equal values need a slower fallback that the cases here never trigger.

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

print("empty list:", search([], 3))
print("single value found:", search([5], 5))
print("single value missing:", search([5], 3))
print("target at the drop point:", search([4, 5, 6, 7, 0, 1, 2], 0))
print("first value:", search([4, 5, 6, 7, 0, 1, 2], 4))
print("last value:", search([4, 5, 6, 7, 0, 1, 2], 2))

The empty row answers minus 1 because the loop never runs. The drop-point row is the value right after the largest value. It is the position a plain sorted search handles worst, and this search finds it directly.