Exercises — Binary search — iterative, recursive; O(log n); searching in sorted - rotated arrays

Binary search needs the array to be sorted ascending so that "middle too small → go right" is valid.

• (a) Ascending → ✔ works.
• (b) Descending, not ascending → ✗ the halving logic points the wrong way. (It would work if you flip every comparison.)
• (c) All equal is a valid non-decreasing (sorted) array → ✔ works; it returns some index holding 3.
• (d) Unsorted → ✗ garbage results.

Answer: works on (a) and (c) only.

lo = 0, hi = 6. Overflow-safe mid: $\text{mid}=lo+\lfloor \frac{hi-lo}{2}\rfloor =0+\lfloor \frac{6-0}{2}\rfloor =3.$ arr[3] = 16. First mid index is 3, value 16.

mid of step 2: $5+\lfloor (9-5)/2\rfloor =5+2=7$. mid of step 3: $5+\lfloor (6-5)/2\rfloor =5+0=5$. Returned index: 5. Three comparisons for 10 elements, matching $\lceil {\log }_{2}10\rceil =4$ as an upper bound. ✔

The window emptied: 40 sits between 38 and 56, so it can't exist. Returned: −1.

Each step does one comparison then halves the window, giving the recurrence (from the parent note) $T(n)=T(n/2)+1,T(1)=1.$ The window shrinks $n\to n/2\to n/4\to \cdots \to 1$. Number of halvings $k$ satisfies $n/2^k=1$, i.e. $2^k=n$, i.e. $k={\log }_{2}n$. Total comparisons $=k+1$. For $n=1000$: ${\log }_{2}1000\approx 9.97$, so at most $\lfloor {\log }_{2}1000\rfloor +1=9+1=10$ comparisons. Answer: 10. (Sanity: $2^{10}=1024\ge 1000$, so 10 halvings suffice.) See Logarithms and Recurrence Relations.

mid = 0 + \lfloor(6-0)/2\rfloor = 3, arr[mid] = 1. Test from the parent note: compare arr[lo] with arr[mid].

• arr[lo] = 6, arr[mid] = 1. Is 6 <= 1? No.
• Because the left endpoint is bigger than the middle, the pivot (the wrap-around point) lies in the left part, so the right half [mid..hi] = [1,2,3,4] is the cleanly sorted one.

Answer: the right half is sorted. (Look at figure below for the picture of why exactly one side stays sorted.)

Returned index: 5. At step 1 we checked the sorted (right) half's range (arr[mid], arr[hi]] = (1, 4]; since 3 lies inside it, we moved right.

Idea: when arr[mid] == target, don't stop — record mid as a candidate and keep searching left (hi = mid - 1) to see if an earlier 2 exists. This connects to Lower & Upper Bound (bisect).

def first_index(arr, target):
    lo, hi, ans = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            ans = mid          # candidate
            hi = mid - 1       # keep looking left
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return ans

Trace on [1,2,2,2,3,4], target 2:

Returned: 1 — the leftmost 2. Still $O(\log n)$: every step halves the window.

Idea: the minimum is the only element smaller than its predecessor. Compare arr[mid] to arr[hi]:

• if arr[mid] > arr[hi], the dip (minimum) is to the right of mid → lo = mid + 1.
• else the minimum is at mid or to its left → hi = mid (keep mid, it may be the min).

def min_index(arr):
    lo, hi = 0, len(arr) - 1
    while lo < hi:              # stop when they meet
        mid = lo + (hi - lo) // 2
        if arr[mid] > arr[hi]:
            lo = mid + 1
        else:
            hi = mid           # note: no -1 here
    return lo

Trace on [4,5,6,7,0,1,2]:

Returned index: 4 (value 0, the minimum). Here hi = mid (no −1) is correct because mid is still a min candidate, and the loop guard is lo < hi (not <=) — otherwise hi = mid with lo == hi never shrinks and loops forever.

Why it breaks: with duplicates, arr[lo] == arr[mid] == arr[hi] can happen while the sorted half is genuinely not the left one. Here arr[0]=2, arr[2]=2 (a mid), arr[5]=2 — the equality 2 <= 2 wrongly claims "left half sorted," and we'd discard the half that actually holds 0.

Patch: when arr[lo] == arr[mid] == arr[hi], we cannot tell which side is sorted, so we shrink both ends by one and retry:

def search_rot_dup(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] == arr[mid] == arr[hi]:
            lo += 1; hi -= 1                 # can't decide — trim both
        elif arr[lo] <= arr[mid]:            # left sorted
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                # right sorted
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Trace on [2,2,2,0,2,2], target 0:

Returned index: 3.

Complexity note: the trim-both branch is what breaks the clean logarithm — in the pathological all-equal case (e.g. [2,2,2,2,2] searching 3) it degrades to $O(n)$. So worst case is $O(n)$ with duplicates, average still near $O(\log n)$.

Problem: ordinary binary search needs hi = n-1, but n is unknown. We must first find a valid hi whose value is $\ge x$, then binary search in [lo, hi].

Phase 1 — exponential expansion (galloping): start lo=0, hi=1. While get(hi) < x, set lo = hi and hi *= 2. Doubling means after $k$ steps hi = 2^k, so we reach past position p in $\lceil {\log }_{2}p\rceil$ steps — this is $O(\log p)$, and it's why doubling (not adding a fixed amount) is essential. Phase 2 — ordinary binary search on [lo, hi]; that window has width $\le 2p$, so it costs $O(\log p)$ too. Total $O(\log p)$.

def search_unbounded(get, x):
    lo, hi = 0, 1
    while get(hi) < x:          # phase 1: find a hi with get(hi) >= x
        lo = hi
        hi *= 2
    while lo <= hi:             # phase 2: normal binary search
        mid = lo + (hi - lo) // 2
        v = get(mid)
        if v == x:
            return mid
        elif v < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Worked check: stream [1,3,7,9,12,15,...] (get past end = ∞), target 12 at index 4. Phase 1: get(1)=3 < 12 → lo=1,hi=2; get(2)=7 < 12 → lo=2,hi=4; get(4)=12, not < 12, stop. Window [2,4]. Phase 2: mid = 2+1 = 3, get(3)=9 < 12 → lo=4; mid=4, get(4)=12 → return 4. ✔

Loop guard vs update pairing ::: lo <= hi needs mid + 1 / mid - 1 shrinking; lo < hi allows hi = mid. Never mix them. Rotated with duplicates worst case ::: $O(n)$, because the all-equal case forces linear trimming. Unbounded search boundary trick ::: exponential doubling of hi, giving $O(\log p)$.