Binary Search

Halving the Search Space · O(log n)

1:00

How binary search halves the search space each step to find a target in O(log n) comparisons on sorted data.

By the end, you can

State the two prerequisites for binary search and explain why each is necessary.
Trace binary search step by step on a small array, tracking `lo`, `mid`, and `hi`.
Calculate the worst-case comparison count using `floor(log2 n) + 1`.
Explain why the algorithm is O(log n) and contrast it with O(n) linear search.
Identify and fix the integer-overflow bug in the midpoint formula.
Recognize off-by-one errors in the loop condition and pointer updates.
Decide when binary search is inappropriate (unsorted data, linked lists) and name alternatives (hash table, lower_bound/upper_bound for duplicates).

Up next in Searching & Sorting