Lesson notes
These notes explain the problem and current implementation. They are a reading companion, not a verbatim transcript of the recording.
Logarithmic time appears when an algorithm repeatedly reduces its remaining work by a constant factor. If each step halves a collection, the number of steps grows slowly even when the collection becomes large. The recording connects this process to logarithms so the notation follows from the work instead of becoming a formula to memorize.
Count the reductions on a small example
Start with 32 candidates. Halving leaves 16, then 8, 4, 2, and 1. Five reductions are enough because 2 to the fifth power is 32. Starting with 64 candidates adds one reduction. Doubling the input therefore adds roughly one step rather than doubling the work.
The logarithm's base reflects the reduction factor. Reducing by thirds gives a different exact count from reducing by halves, but those logarithms differ by a constant multiplier. Big O discards that constant, so both can be written O(log n) when the reduction factor stays fixed.
Include the work inside each reduction
A binary search uses bounded work to examine a midpoint and select a remaining interval. If instead each level scans the entire remaining interval, the total cost needs an additional sum. Repeatedly halving the input does not by itself prove logarithmic time; it only bounds how many reduction levels occur.
Storage also depends on implementation. An iterative search can track two boundaries and a midpoint with constant auxiliary space. A recursive version keeps an active call chain. Creating a fresh slice at every call introduces copying and allocation that an index-boundary version avoids.
Check whether the structure stays balanced
A balanced binary search tree has logarithmic height. An ordinary unbalanced tree built from sorted inserts can become a chain and have linear height. The search rule alone does not guarantee a logarithmic path. State the balance assumption when comparing tree operations with binary search over a sorted array.
Practice Searching and Binary Search with a target below every value, above every value, and absent between two values. Write the candidate interval after each step and explain why the discarded portion cannot contain the target. The Big O visualizer lets you compare logarithmic growth with linear and quadratic models without treating those models as machine benchmarks.