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

Before we start, one reminder of the three moving parts (all defined in the parent):

lo — the left edge of the window we still trust to maybe hold the target.
hi — the right edge of that window.
mid — the element half-way between them, computed as mid = lo + (hi - lo) // 2.
n — the length (number of elements) of the array. Indices run from 0 to n - 1, so the very first window is lo = 0, hi = n - 1.

The window [lo, hi] is the promise "if the target exists, it is somewhere in here." Every step shrinks it.

Both blocks below run this exact loop — keep it in view; every worked step is just one turn of it:

def bsearch(arr, target):
    lo, hi = 0, len(arr) - 1        # n = len(arr); window is [0, n-1]
    while lo <= hi:                 # guard: window still has >= 1 element
        mid = lo + (hi - lo) // 2   # overflow-safe midpoint (see note above)
        if arr[mid] == target:
            return mid              # hit
        elif arr[mid] < target:
            lo = mid + 1            # discard mid and everything left of it
        else:
            hi = mid - 1            # discard mid and everything right of it
    return -1                       # window emptied -> not present

Intuition Why the guard is

lo <= hi, and why the loop is guaranteed to STOP Read the window as the set of indices {lo, lo+1, ..., hi}. How many indices is that? Exactly hi - lo + 1.

When lo == hi, that count is 1 — there is still one untested element. If we stopped at lo < hi we would walk away before checking it, missing single-element matches. So the guard must be <=, not <.
When lo > hi, the count hi - lo + 1 is 0 or negative — the window is empty, so there is genuinely nothing left; we return -1.
Termination proof (why it can't loop forever): every branch that does not return strictly shrinks the window. lo = mid + 1 raises lo past mid; hi = mid - 1 lowers hi below mid. Because mid always lies inside [lo, hi], each move drops the count hi - lo + 1 by at least one. A count that strictly decreases and can never go below zero must hit "empty" in finitely many steps. That is the whole reason the +1 / -1 matter: without them the window could stall and the loop would spin forever.

And the rotated variant (used in Ex 6–9), which first names the sorted half:

def search_rotated(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]:                 # LEFT half is sorted
            if arr[lo] <= target < arr[mid]:    # target lies inside it
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                   # RIGHT half is sorted
            if arr[mid] < target <= arr[hi]:    # target lies inside it
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

Intuition Why

arr[lo] <= arr[mid] tells you the LEFT half is sorted A rotated sorted array has exactly one "cliff" — the single place where a big number is immediately followed by a small one (in [15,18,2,3,6,8,11] the cliff is 18 → 2). That cliff is the only thing that breaks sortedness. Now split at mid into the left span [lo..mid] and the right span [mid..hi]. The cliff sits in one of them, never both.

If the cliff is not in the left span, then [lo..mid] climbs steadily, so its first element is its smallest: arr[lo] <= arr[mid]. Sorted-left detected.
If the cliff is in the left span, it drags a small value below arr[lo] down into the middle, so arr[lo] > arr[mid]. Then the cliff cannot also be on the right, so the right span is the clean sorted one. That is the whole derivation: comparing just the two edge values arr[lo] and arr[mid] reveals which side is cliff-free, i.e. sorted. Once we know a side is sorted, we can range-check the target there with ordinary </<=. Why <= and not <? When the window shrinks to size 1 or 2, lo can equal mid; then arr[lo] <= arr[mid] is trivially true (a single element is sorted), keeping that edge case correct.

The scenario matrix

Every binary-search problem you will ever be handed falls into exactly one of these cells. The job of this page is to leave no cell un-worked.

#	Cell (what makes it special)	Array kind	Worked in
C1	Target sits in the middle — found on step 1	plain sorted	Ex 1
C2	Target at the first index (left boundary)	plain sorted	Ex 2
C3	Target at the last index (right boundary)	plain sorted	Ex 2
C4	Target absent, between two values → `-1`	plain sorted	Ex 3
C5	Target smaller than everything / larger than everything (out of range)	plain sorted	Ex 3
C6	Degenerate: empty array, single element	plain sorted	Ex 4
C7	Duplicates — which index do we get?	plain sorted	Ex 5
C8	Rotated, target in the un-sorted half	rotated	Ex 6
C9	Rotated, target in the sorted half	rotated	Ex 6
C10	Rotated, zero rotation (array not actually turned)	rotated	Ex 7
C11	Real-world word problem (mapping a story to indices)	plain sorted	Ex 8
C12	Exam twist — count steps / find the pivot	rotated	Ex 9

We will hit all twelve in nine examples.

The figure below is our map of the scenario matrix. It draws the workhorse array as ten cyan-outlined boxes on the blueprint grid, each labelled with its value on top and its index [0]..[9] underneath. Three amber arrows point down onto boxes — these are the cells where the search lands on a real element: the left one labelled "first index (C2)" hits box [0] (value 2), the centre one "middle hit (C1)" hits box [4] (value 16), the right one "last index (C3)" hits box [9] (value 91). Three cyan arrows point at empty space — these are the misses: one rises from the seam between boxes [4] and [5] labelled "gap = miss (C4) 20?" (there is no box there, so 20 falls through), one sits left of box [0] labelled "< all (C5) 1?", and one sits right of box [9] labelled "> all (C5) 100?". The lesson the picture teaches at a glance: amber = a box to land on, cyan = no box exists, which is exactly why those searches run the window off an end.

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

Plain sorted array examples

We use one workhorse array for the first block:

$arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]$

Here $n = 10$ , indices 0..9. Since $2^{3} = 8 < 10 \leq 16 = 2^{4}$ , the worst case is $⌈ lo g_{2} 10 ⌉ = 4$ comparisons.

Worked example Ex 2 — C2 & C3: boundaries →

find 2 (first) and find 91 (last) Forecast: boundaries are the classic "off-by-one" trap. Will the loop reach index 0 and index 9?

Finding 2 (leftmost):

lo=0, hi=9, mid=4. arr[4]=16 > 2 → hi = mid-1 = 3. Why? 16 overshot, so 2 (if present) is strictly left of mid; we drop mid and everything right of it.
lo=0, hi=3, mid=1. arr[1]=5 > 2 → hi = 0. Why? Same reasoning — keep shrinking toward the left.
lo=0, hi=0, mid=0. arr[0]=2 → return 0. Why? Window collapsed to a single element [0,0]; because the guard is lo <= hi, we still test it.

Finding 91 (rightmost):

lo=0, hi=9, mid=4. arr[4]=16 < 91 → lo = 5. Why? 16 is smaller than 91, so 91 (if present) must lie strictly to the right of mid; we discard mid and everything left of it by moving lo up.
lo=5, hi=9, mid=7. arr[7]=56 < 91 → lo = 8. Why? Same logic on the shrunken window — 56 is still below 91, so keep pushing lo rightward.
lo=8, hi=9, mid=8. arr[8]=72 < 91 → lo = 9. Why? 72 < 91 again; only index 9 can still hold the target, so lo climbs to it.
lo=9, hi=9, mid=9. arr[9]=91 → return 9. Why? Window is the single cell [9,9]; the lo <= hi guard lets us test it, and it matches.

Verify: arr[0]=2, arr[9]=91. Both edges reachable because lo <= hi never abandons the last element. ✓

Worked example Ex 3 — C4 & C5: absent values →

find 20, find 1, find 100 Forecast: three misses. One is between neighbours, two are outside the whole range. Each must land on -1.

find 20 (between 16 and 23 — C4):

lo=0,hi=9,mid=4, arr[4]=16 < 20 → lo=5. Why? 16 < 20, so 20 (if present) is right of mid; discard the left half.
lo=5,hi=9,mid=7, arr[7]=56 > 20 → hi=6. Why? 56 > 20, so 20 must be left of this mid; discard the right half.
lo=5,hi=6,mid=5, arr[5]=23 > 20 → hi=4. Why? 23 > 20, so 20 would be left of index 5 — but that pushes hi below lo.
Now lo=5 > hi=4 → window empty → return -1. Why? 20 would have to sit between indices 4 and 5, but there is no slot there — the array excludes it.

find 1 (below everything — C5):

lo=0,hi=9,mid=4, 16>1 → hi=3. Why? 16 > 1, so 1 is left of mid; drop the right half.
lo=0,hi=3,mid=1, 5>1 → hi=0. Why? 5 > 1, keep shrinking leftward.
lo=0,hi=0,mid=0, 2>1 → hi=-1. Why? Even the smallest element arr[0]=2 overshoots 1, so hi steps to -1, off the left edge.
lo=0 > hi=-1 → return -1. Why? The window walked off the left edge; nothing is smaller than arr[0].

find 100 (above everything — C5): mirror image — every mid value is below 100, so each step does lo = mid+1, pushing lo up through 5, 8, 10. Why each step? 100 is bigger than every element, so the target (if it existed) would always be to the right, and lo marches until lo = n = 10 > hi = 9 → return -1.

Verify: none of 20, 1, 100 is in arr, so -1 each time. ✓ Notice the window can empty in three ways: crossing in the middle, falling off the left (hi=-1), falling off the right (lo = n, i.e. lo = 10).

Worked example Ex 4 — C6: degenerate sizes → empty

[] and single [42] Forecast: what happens when there is nothing to split, or only one thing?

Empty arr = [], find 5:

lo=0, hi = n-1 = -1 (since n = 0). Guard lo <= hi is 0 <= -1 → false, loop body never runs → return -1. Why this step? With no elements the window is empty from the start; the guard protects us — no crash, no bad index.

Single arr = [42], find 42:

lo=0, hi=0, mid=0, arr[0]=42 → return 0. Why? n = 1, so the window is the single cell [0,0]; lo <= hi lets us test it and it matches.

Single arr = [42], find 7:

lo=0, hi=0, mid=0, arr[0]=42 > 7 → hi=-1. Why? 42 > 7, so 7 (if present) is left of index 0; hi drops to -1.
lo=0 > hi=-1 → return -1. Why? Window emptied — the only element was ruled out.

Verify: empty → -1; hit → 0; miss → -1. The lo <= hi guard makes size-0 and size-1 fall out for free. ✓

Rotated array examples

Recall from the parent: a rotated sorted array is a sorted array cut at one point and its front moved to the back, e.g. [4,5,6,7,0,1,2]. It is not globally sorted, but at least one side of mid is always sorted — the fact we derived above.

The figure below shows exactly how the rotated test reads. It draws rot = [15,18,2,3,6,8,11] as seven boxes with indices [0]..[6] underneath. The two amber-outlined boxes on the left (15, 18) are the "wrapped-high" front — the piece that used to be at the end and got moved forward. The five cyan-outlined boxes (2,3,6,8,11) are the sorted tail. A white arrow drops onto box [3] labelled "mid = 3, arr[mid]=3". Underneath the boxes are two coloured spans: an amber line under [0..3] labelled "left half: NOT sorted (pivot 18→2 inside)" — it crosses the cliff, so it is not sorted — and a cyan line under [3..6] labelled "right half: SORTED 3 < 6 < 8 < 11". Across the top, a white caption states the exact decision the code makes: "arr[lo]=15 > arr[mid]=3 ⇒ right side is the clean one." Read the picture as: whenever the left edge value exceeds the mid value, the cliff hides on the left, so trust the right span.

We use $rot = [15, 18, 2, 3, 6, 8, 11]$ (indices 0..6, original sorted order rotated so that 15, 18 moved to the front).

Worked example Ex 6 — C8 & C9: rotated, both half-cases →

find 6 then find 18 Forecast: for 6, the sorted half will be the right side; for 18, it will be the left side. Watch which branch fires.

find 6 (target ends up in a sorted right half — C8/C9):

lo=0, hi=6, mid=3. arr[3]=3. Not equal. Is arr[lo]=15 <= arr[mid]=3? No → the right half [3..6] is the sorted one. Why? If the left edge is bigger than mid, the cliff (the wrap-around drop) must be inside the left half, so the right half is clean and sorted.
Right half sorted → check arr[mid]=3 < 6 <= arr[hi]=11? Yes → target is in the right → lo = mid+1 = 4. Why? In a sorted half we can range-check with plain </<=: since 6 lies between arr[mid] and arr[hi], it must be to the right of mid, so discard mid and everything left.
lo=4, hi=6, mid=5. arr[5]=8. Not equal. arr[lo]=6 <= arr[mid]=8? Yes → left half [4..5] sorted. Why? Now the left edge is not bigger than mid, so no cliff sits in the left span; that span is sorted.
Is arr[lo]=6 <= 6 < arr[mid]=8? Yes → target in left → hi = mid-1 = 4. Why? 6 lies in the sorted left range [6, 8), so it is at or left of mid; discard mid and everything right.
lo=4, hi=4, mid=4. arr[4]=6 → return 4. Why? Window collapsed to the single cell [4,4]; lo <= hi lets us test it and it matches.

find 18 (target ends up in a sorted left half — C9):

lo=0, hi=6, mid=3, arr[3]=3. Not equal. Is arr[lo]=15 <= 3? No → right half [3..6] sorted. Why? Same detector as before: left edge bigger than mid means the cliff is on the left, so the right half is clean.
Is arr[mid]=3 < 18 <= arr[hi]=11? No → target NOT in the sorted right → hi = mid-1 = 2. Why? 18 falls outside the sorted right range (3, 11], so it cannot be there; the only place left is the (unsorted) left half, so shrink hi.
lo=0, hi=2, mid=1, arr[1]=18 → return 1. Why? New mid lands directly on 18; equality returns immediately.

Verify: rot[4]=6, rot[1]=18. ✓ In every step we first named the sorted half, then used plain range logic there.

Worked example Ex 7 — C10: rotated by zero →

find 8 in [2,3,6,8,11,15,18] Forecast: "rotated by 0" means it is still fully sorted — there is no cliff at all. Does the rotated algorithm still work, or does it need a special case?

lo=0, hi=6, mid=3. arr[3]=8 == 8 → return 3. Why this step? mid=3 happens to land on the target directly, so equality returns at once — no half-picking needed this time.

Now trace find 15 in the same array to exercise the branch logic when there's no lucky centre hit:

lo=0, hi=6, mid=3. arr[3]=8. Not equal. Is arr[lo]=2 <= arr[mid]=8? Yes → left half [0..3] sorted. Why? With zero rotation the whole array is sorted, so arr[lo] <= arr[mid] is always true — the "left half sorted" branch fires every single time, exactly like ordinary binary search.
Is arr[lo]=2 <= 15 < arr[mid]=8? No (15 is not below 8) → target not in the sorted left → lo = mid+1 = 4. Why? 15 lies outside the left range [2, 8), so discard the left half by raising lo.
lo=4, hi=6, mid=5. arr[5]=15 → return 5. Why? New mid lands on 15; equality returns.

Verify: arr[3]=8 and arr[5]=15. ✓ Key lesson: the rotated algorithm is a superset — with zero rotation the arr[lo] <= arr[mid] test is always true, so it degrades gracefully into plain binary search with no extra code.

Worked example Ex 8 — C11: real-world word problem

Story: A library shelf holds books sorted by their 13-digit ISBN. The shelf currently has ISBN codes (last 3 digits shown) [104, 219, 337, 402, 588, 613, 771, 890] at slots 0..7. A robot must fetch the book with code 588. How many shelf-slots does it physically open?

Forecast: 8 books, so worst case $⌈ lo g_{2} 8 ⌉ = 3$ opens. Will 588 need all three?

Map the story to indices. "sorted by ISBN" = sorted array; "fetch code 588" = target=588. Here n = 8, so lo=0, hi=7. Why? Binary search only applies once we confirm the data is sorted — the problem states it is.
mid = 0+(7-0)//2 = 3 (since 7 // 2 = 3). arr[3]=402 < 588 → lo=4. (open #1) Why? 402 is below 588, so the book (if shelved) is to the right of slot 3; discard slots 0–3 by raising lo.
lo=4, hi=7, mid=5. arr[5]=613 > 588 → hi=4. (open #2) Why? 613 overshoots 588, so the book is to the left of slot 5; discard slots 5–7 by lowering hi.
lo=4, hi=4, mid=4. arr[4]=588 → return 4. (open #3) Why? Window is the single slot [4,4]; lo <= hi lets the robot open it, and it is the book.

Verify: arr[4]=588, found in 3 opens. Units check: "opens" = comparisons, and $3 \leq ⌈ lo g_{2} 8 ⌉ = 3$ . ✓ Compare with Linear Search: the robot would have opened 5 slots (0..4) scanning left-to-right.

Worked example Ex 9 — C12: exam twist → find the

pivot (smallest element) of a rotated array Statement: In rot = [15, 18, 2, 3, 6, 8, 11], find the index of the minimum without scanning all elements. (This is the rotation point — the bottom of the cliff, where the original array wrapped.)

Forecast: the minimum is the one spot where a bigger number is immediately followed by a smaller one. Can we binary-search that? Yes — compare arr[mid] to arr[hi].

lo=0, hi=6, mid=3. arr[3]=3 vs arr[hi]=arr[6]=11. Is arr[mid] > arr[hi]? 3 > 11? No → the minimum is at mid or to its left → hi = mid = 3. Why this step? If arr[mid] <= arr[hi], the right side [mid..hi] is sorted (no cliff), so its smallest is arr[mid] itself; we never need to look right of mid — but we keep mid (no -1) because mid might BE the minimum.
lo=0, hi=3, mid=1. arr[1]=18 vs arr[3]=3. Is 18 > 3? Yes → minimum is strictly to the right → lo = mid+1 = 2. Why? arr[mid]=18 is bigger than the right edge arr[hi]=3, so the cliff lies to the right of mid; mid cannot be the minimum, hence +1.
lo=2, hi=3, mid=2. arr[2]=2 vs arr[3]=3. 2 > 3? No → hi = mid = 2. Why? arr[mid]=2 <= arr[hi]=3, so the right side is sorted and the minimum is at mid or left of it; keep mid, shrink hi to it.
lo=2, hi=2 → window is one element → return 2. Why? When lo == hi the search space is a single index, which must be the minimum we cornered; the lo < hi loop stops here.

Verify: rot[2]=2, which is indeed the smallest value in rot; the array was rotated by 2 positions. ✓ Still $O (lo g n)$ — each step halves the window. This is the trick a Binary Search Tree does not need (its structure already encodes order), but here we recover the pivot with the same halving idea.

Case coverage checklist

Recall Did we really hit every cell?

Middle hit ::: Ex 1 (C1) First / last index ::: Ex 2 (C2, C3) Absent between two values ::: Ex 3 (C4) Out of range both sides ::: Ex 3 (C5) Empty and single-element ::: Ex 4 (C6) Duplicates ::: Ex 5 (C7) Rotated, unsorted half ::: Ex 6 (C8) Rotated, sorted half ::: Ex 6 & 7 (C9) Rotated by zero ::: Ex 7 (C10) Word problem ::: Ex 8 (C11) Exam twist (find pivot) ::: Ex 9 (C12)

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