DSA Searching a Rotated Array with Duplicates

The problem

Searching a rotated array with duplicates asks whether a target value appears in the array. A rotated array is a sorted array cut once and swapped in two parts. Values may repeat.

The answer is True or False. There is no index to report and no count. The cases below are the ones this article solves.

cases = [
    ([2, 5, 6, 0, 0, 1, 2], 0, True),
    ([2, 5, 6, 0, 0, 1, 2], 3, False),
    ([1, 0, 1, 1, 1], 0, True),
    ([1, 3, 1, 1, 1], 3, True),
    ([1, 1, 1, 1, 1], 2, False),
]
for nums, target, expected in cases:
    print("nums", nums, "target:", target, "present:", expected)

The third case is the hard shape. The single 0 hides among four 1s, and the first probe of any halving search lands on a 1.

Intuition: reuse the search for distinct values

The first idea reuses the binary search that works when all values differ. That search certifies one half as sorted and tests whether the target fits inside it. The other half is discarded.

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

print("distinct [4, 5, 6, 7, 0, 1, 2], target 0:", search_distinct([4, 5, 6, 7, 0, 1, 2], 0))
print("duplicates [1, 0, 1, 1, 1], target 0:", search_distinct([1, 0, 1, 1, 1], 0))
print("true answer for the second search:", 0 in [1, 0, 1, 1, 1])

The distinct-value search reports False on an array that holds the target. The left end, middle and right end all read 1. That agreement certifies neither half as sorted, yet the search trusts the left half and discards the side holding the 0.

Brute force: scan every value

The brute force compares the target against each value in order. It cannot be fooled by repeats. A counter records the comparisons.

def search_brute(nums, target):
    checks = 0
    for value in nums:
        checks += 1
        if value == target:
            return True, checks
    return False, checks

cases = [([2, 5, 6, 0, 0, 1, 2], 0), ([2, 5, 6, 0, 0, 1, 2], 3), ([1, 0, 1, 1, 1], 0), ([1, 3, 1, 1, 1], 3), ([1, 1, 1, 1, 1], 2)]
for nums, target in cases:
    found, checks = search_brute(nums, target)
    print("nums", nums, "target:", target, "found:", found, "checks:", checks)

A miss pays the full length every time. A hit pays its position. Nothing about the rotation helps or hurts the scan.

The optimal solution: shrink when the ends agree

The fix checks one extra case before the sorted-half test. When the left end, middle and right end all agree, the search shrinks both ends by one step. That one sentence is the whole change.

Shrinking is safe at that moment. The middle was already compared with the target and missed, so the target differs from the agreeing value. The two discarded ends hold only copies of that value.

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

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

All five cases pass. Once the ends disagree again, the usual sorted-half test resumes and the range halves. Only total agreement costs the slow shrink.

Walkthrough: hunting 0 in [1, 0, 1, 1, 1]

The first probe hits the trap head-on. All three probed values are 1, and the target is 0. The trace prints the range, the middle value, and the move at each step.

def traced_search(nums, target):
    lo = 0
    hi = len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        print("range", lo, "to", hi, "- middle value", nums[mid], end=" ")
        if nums[mid] == target:
            print("-> found")
            return True
        if nums[lo] == nums[mid] == nums[hi]:
            print("-> ends and middle agree, shrink both ends")
            lo += 1
            hi -= 1
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                print("-> left half is sorted and holds the target range")
                hi = mid - 1
            else:
                print("-> left half is sorted, target is elsewhere")
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                print("-> right half is sorted and holds the target range")
                lo = mid + 1
            else:
                print("-> right half is sorted, target is elsewhere")
                hi = mid - 1
    print("range empty -> not found")
    return False

print("result:", traced_search([1, 0, 1, 1, 1], 0))

One shrink clears the blur. The next probe can certify the left half as sorted, and the probe after that lands on the 0. The answer is read off the trace.

Complexity

When the ends keep disagreeing, the range halves every step and the time is O(log n). When every value is equal and the target is absent, each step only shrinks, and the worst-case time is O(n).

The search stores only its range ends, so its extra space is O(1). The counts below run the counted search on both shapes at three sizes, hunting a target that is not there.

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

for size in [8, 128, 2048]:
    base = list(range(size))
    rotated = base[size // 3:] + base[:size // 3]
    _, distinct_steps = counted_search(rotated, -1)
    _, equal_steps = counted_search([7] * size, 2)
    print("size:", size, "- distinct steps:", distinct_steps, " all-equal steps:", equal_steps)

The distinct column barely moves as the size multiplies by sixteen. The all-equal column grows with the size itself, because each shrink discards only two positions.

Edge cases and pitfalls

An empty array answers False at once. A single value is a plain comparison. A target equal to the repeated value is found on the first probe, before any shrink is considered.

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

print("empty array:", search([], 1))
print("single value, hit:", search([5], 5))
print("single value, miss:", search([5], 1))
print("target is the repeated value:", search([3, 1, 3, 3, 3], 3))
print("hidden minimum as target:", search([2, 2, 2, 0, 2], 0))
print("target at the seam:", search([4, 5, 6, 1, 2], 4))

The order inside the loop is a pitfall of its own. The target check must run before the shrink test. A middle value equal to the target ends the search there, and shrinking first could discard the very copy just probed at an end.