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

We assume only this: you can count, and you know "sorted" means each number is $\ge$ the one before it. Every symbol below is defined the moment it appears.

Step 1 — What a "sorted list" and an "index" even are

WHAT. A list is a row of boxes. Each box holds a number. The position of a box, counting from $0$ on the left, is its index. So in the row below, the box at index $3$ holds the value $7$.

WHY start here. The whole algorithm talks about indices (lo, hi, mid) — positions, not values. If we blur "position" and "value" together, nothing later makes sense. So we nail the vocabulary first.

PICTURE. The blue numbers under the boxes are indices; the white numbers inside are values. Notice the values only ever go up as you move right — that "only goes up" property is the single thing binary search will exploit.

Step 2 — The window [lo, hi]: the region still worth searching

WHAT. We draw two markers. $lo$ (chalk-blue, left) and $hi$ (chalk-pink, right). Together they fence off a stretch of boxes called the window. At the start the window is the whole list: $lo=0$, $hi=n-1$, where $n$ is how many boxes there are.

$lo=0,hi=\underset{\text{count of boxes}}{\underbrace{n}}-1$

Here $n-1$ is the index of the last box — because we started counting at $0$, the last position is one less than the count.

WHY a window. We are going to promise ourselves one thing and never break it:

PICTURE. The shaded band between the blue and pink arrows is the window. Boxes outside it are greyed — already proven irrelevant.

Step 3 — Why we cut at the middle, and how to compute it safely

WHAT. We pick one box inside the window to test: the middle, at index $mid$.

$mid=lo+\lfloor \frac{hi-lo}{2}\rfloor$

Reading it term by term:

• $hi-lo$ = how wide the window is (a distance).
• $\lfloor \frac{\cdot }{2}\rfloor$ = half that distance, rounded down (the $\lfloor \rfloor$ floor brackets mean "throw away the fraction"). Rounding down guarantees $mid$ is a real index, never off the right edge.
• $lo+(\dots )$ = start at the left marker, walk halfway in. That lands us in the centre.

WHY the middle and not, say, one-third? After we test $mid$ we throw away everything on one side of it. The side we keep could be either side. To make the worst outcome as small as possible, we want both sides equal — and equal halves happen only when we cut in the centre. Any other cut leaves one side bigger, and the enemy (worst case) always hands you the bigger side.

WHY not the simpler $\frac{lo+hi}{2}$? Algebraically it's the same number: $lo+\frac{hi-lo}{2}=\frac{2lo+hi-lo}{2}=\frac{lo+hi}{2}.$ But $lo+hi$ can be a huge sum that overflows a fixed-width integer, while $hi-lo$ is always smaller than $hi$, so it can never overflow. Same value, safer road.

PICTURE. The yellow arrow drops onto the centre box. The two brackets show the equal-ish left and right halves it creates.

Step 4 — The three comparisons: which half dies

WHAT. We compare the value at $mid$ to the target $t$. Exactly three things can happen, and each has a forced response that keeps the promise from Step 2.

• $arr[mid]<t$: the middle value is too small. Since the list only goes up rightward, everything at or left of $mid$ is also too small. So the target, if it exists, is strictly to the right → move $lo$ past $mid$.
• $arr[mid]>t$: mirror image, target is to the left → pull $hi$ before $mid$.

WHY the $\pm 1$ (not lo = mid)? We already tested $mid$ — it's not the answer. Re-including it wastes a comparison and, worse, if the window is size $1$ or $2$ the marker may never move, and the loop spins forever. The $\pm 1$ physically shrinks the window, guaranteeing progress.

PICTURE. Three mini-rows, one per case. Greyed boxes = the half we just discarded; the markers have jumped to hug what survives.

Step 5 — When to stop: lo <= hi

WHAT. We repeat Steps 3–4 while the window is non-empty. A window is non-empty exactly when $lo\le hi$. The moment $lo>hi$, the fence has crossed — no boxes are left inside — and we return $-1$ ("not found").

WHY <= and not <? When $lo=hi$ the window still holds one untested box. Stopping at $lo<hi$ would skip it and could miss a single-element match. The equals sign keeps that last box alive.

PICTURE. Left panel: $lo=hi$, one lonely box still inside — we must test it. Right panel: markers have crossed, the band is empty, so the search is over.

Step 6 — Counting the steps: where ${\log }_{2}n$ is born

WHAT. Each pass through Steps 3–4 does a fixed amount of work (one comparison, one marker move) and then leaves us with at most half the boxes. Call $T(n)$ the number of comparisons needed, worst case, for a window of $n$ boxes:

$T(n)=\underset{\text{the surviving half}}{\underbrace{T\left(\frac{n}{2}\right)}}+\underset{\text{this step’s comparison}}{\underbrace{1}},T(1)=1.$

WHY this equation gives a logarithm. Ask: how many times can I halve $n$ before I reach a single box? Say it takes $k$ halvings:

$\frac{n}{2^k}=1\Rightarrow 2^k=n\Rightarrow k={\log }_{2}n.$

That last line is the definition of a logarithm: ${\log }_{2}n$ asks "$2$ to what power gives $n$?" — and "what power" is exactly "how many halvings." (The recurrence itself is a recurrence relation; solving it is what gives the $\log$.) So:

$\boxed{T(n)={\log }_{2}n+1=O(\log n)}$

which the parent formalises under Big-O.

PICTURE. A staircase of shrinking windows: $16\to 8\to 4\to 2\to 1$. Count the steps down the stairs — that count is the height of the tree, and the height is ${\log }_{2}n$.

Step 7 — The rotated array: at least one half is still sorted

WHAT. Take a sorted list and "rotate" it: cut it somewhere and swap the two pieces, e.g. [4,5,6,7,0,1,2]. It's no longer sorted overall — but look closely: on either side of any $mid$, at least one half is still perfectly sorted. We detect which by comparing the window's left value to its middle value:

$arr[lo]\le arr[mid]\Rightarrow \text{left half is sorted}.$

If the left value is $\le$ the middle value, nothing "wrapped around" between them, so that stretch rises cleanly — it's sorted. Otherwise the wrap (the pivot) sits on the left, which forces the right half to be the clean sorted one.

WHY it still halves. Once we know which half is sorted, we can use ordinary range-checking ("is $t$ between these two endpoints?") to decide whether the target lives in the sorted half. Either way we discard one half → still $O(\log n)$.

WHY the $\le$ (not $<$). When the window shrinks so $lo=mid$, the "left half" is a single box — trivially sorted — and $arr[lo]\le arr[mid]$ becomes $arr[lo]\le arr[lo]$, which is true. The equals sign keeps that boundary case correct.

PICTURE. The rotated row with the pivot (the drop from $7$ to $0$) marked in pink. The yellow bracket highlights the clean sorted half around a sample $mid$.

The one-picture summary

WHAT. One figure stitches the whole journey together: the window narrowing, the middle cut, a half discarded each pass, and the step-count collapsing to ${\log }_{2}n$.

Flashcards