Lesson 27 of 48
Sorting and searching under constraint
Real problems, with a time and space budget.
Binary search is four lines and notoriously easy to get wrong at the boundaries. Proving it against brute force on thousands of random cases is the habit that separates code you believe from code you have checked.
Do this
Implement binary search and prove it with a randomised test against a brute-force scan over thousands of cases — including empty input, a single element, and the value absent.
The question that unlocks the next lesson
Binary search requires which precondition?
- AThe array is sorted
- BThe array has no duplicates
- CThe array length is a power of two
- DThe values are numeric