test_reference_grid_numline

The maze: 0 = open, 1 = wall (dimmed). We start BFS from cell $(0,0)$.

Initialize BFS. Mark $(0,0)$ as the starting cell (blue = current frontier).

Dequeue $(0,0)$ (green = visited). Expand south to $(1,0)$. Wall at $(0,1)$ blocks east.

Dequeue $(1,0)$. Expand south to $(2,0)$. Walls block east at $(1,1)$.

Dequeue $(2,0)$. Expand east to $(2,1)$ and $(2,2)$. Wall at $(3,0)$ blocks south.

Dequeue $(2,1)$ and $(2,2)$. Discover $(3,2)$ southward and $(1,2)$ northward.

Expand further. Discover $(3,3)$, $(3,4)$, and $(0,2)$. Getting closer to the goal.

Expand frontier. We reach $(4,4)$ — the goal! BFS guarantees shortest path.

Shortest path found (sky blue): $(0,0) \to (1,0) \to (2,0) \to (2,1) \to (2,2) \to (3,2) \to (3,3) \to (3,4) \to (4,4)$. BFS finds the shortest path in an unweighted grid.

Start binary search for target $= 10$. Full range $[0, 15]$. Compute $mid = \lfloor(0+15)/2\rfloor = 7$.

$mid = 7 < 10$, so target is in the right half. Narrow to $[8, 15]$. New $mid = \lfloor(8+15)/2\rfloor = 11$.

$mid = 11 > 10$, so target is in the left half. Narrow to $[8, 10]$. New $mid = \lfloor(8+10)/2\rfloor = 9$.

$mid = 9 < 10$, go right. Narrow to $[10, 10]$. New $mid = 10$.

$mid = 10 =$ target. Found! Binary search completes in $O(\log n)$ steps.

Summary: we checked $mid = 7, 11, 9, 10$ — only 4 comparisons to find the target in a range of 16 values. This is $\lceil\log_2 16\rceil = 4$ steps.