Practice & recap · Joshua Wong

A small test set

Use examples that force the search to reach its boundaries.

Input	Target	Binary search result	Lower bound result
`[]`	5	`-1`	`0`
`[5]`	5	`0`	`0`
`[5]`	2	`-1`	`0`
`[5]`	9	`-1`	`1`
`[2, 5, 5, 8]`	5	`1` or `2` is a valid match	`1`

The binary-search implementation in the earlier lesson returns index 1 for the last row. The table distinguishes the general contract from one implementation’s choice.

Explain the invariant

Write a sentence describing what is still possible at the start of each iteration. Then explain why each branch preserves that sentence.

Show worked solution

For ordinary binary search: if the target exists, at least one matching position is inside the current inclusive interval. Sorted order lets us exclude the half whose values cannot match. Each unsuccessful comparison removes mid and at least one candidate, so the interval eventually becomes empty.

A compact mathematical recap

This expression connects the size of the remaining interval to the number of halvings. The surrounding region can scroll on a narrow screen.

\underbrace{n}_{\text{initial candidates}} \longrightarrow \underbrace{\left\lfloor n/2 \right\rfloor}_{\text{after one unsuccessful comparison}} \longrightarrow \underbrace{\left\lfloor n/2^k \right\rfloor}_{\text{after }k\text{ unsuccessful comparisons}}

What to carry forward

Binary search needs an ordering property, not just a short loop.
Choose an interval convention and use it consistently.
Specify whether you need any match, the first match, or an insertion point.
Check empty inputs, single elements, absent values, and duplicates.

You have reached the end of this sample curriculum. Return to the overview to revisit any lesson.