Rotated sorted arrays

Understand the idea

A rotated sorted array has a discontinuity, but at least one side of a midpoint remains sorted when values are distinct. Check whether the target lies within that sorted side before choosing which half to retain.

Work through an example

[4,5,6,7,0,1,2] at mid value 7 has a sorted left side. Target 1 is outside [4,7), so retain the right side.

Time and space complexity

O(log n) for distinct values; duplicates can hide the sorted side and force O(n) worst-case shrinking.

Why it works

The target, if present, remains within the active inclusive search interval.

Common mistakes

• Ordinary sorted-array updates are invalid across the rotation.
• Equality at endpoints may make duplicates ambiguous.

Chapter lab · Python implementation

Binary search discards half a monotone candidate domain. The lab uses half-open [lo,hi) lower-bound search. Write the invariant and update rules together; mixing inclusive and half-open conventions creates off-by-one bugs. A logarithmic search does not make list insertion logarithmic.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

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

def exact(values,target):
    i=lower_bound(values,target)
    return i if i<len(values) and values[i]==target else -1

def minimum_capacity(weights,days):
    if days<1 or not weights or any(w<1 for w in weights):
        raise ValueError('positive weights and days required')
    def feasible(capacity):
        used,load=1,0
        for w in weights:
            if load+w>capacity:
                used+=1; load=0
            load+=w
        return used<=days
    lo,hi=max(weights),sum(weights)
    while lo<hi:
        mid=(lo+hi)//2
        if feasible(mid): hi=mid
        else: lo=mid+1
    return lo

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert lower_bound([1,3,3,7],3)==1
assert lower_bound([],5)==0
assert exact([1,3,3,7],4)==-1
assert exact([1,3,3,7],7)==3
assert minimum_capacity([3,2,2,4,1,4],3)==6