Python 7.2The video for this lesson is on its way.
Everything else is ready: study the parts, the key terms and the quiz below.
Python 7.2Code walkthrough8 parts
Binary Search
Find an item in a sorted list in log time.
Loading your progress…Next: 7.3 Hash Tables
In this lesson8 parts
- 01Do we need to look at everything?
- 02Halving the range
- 03Writing it
- 04Why it is O(log n)
- 05It needs a sorted list
- 06bisect
- 07Common mistakes
- 08Where day thirty starts, recap and challenge
Key terms
The words this lesson introduces, each in one line. The module’s glossary collects them all.
- binary search
- Finding a value in a sorted list by comparing it with the middle of the range, and keeping the half that can still hold it.
- logarithmic time
- O(log n): the operations grow by one each time n doubles. Binary search on 1,000,000 values makes at most 20 comparisons.
Quiz 5 questions
Your first pick on each question is the one that counts, and a right one earns a coin. Getting one wrong here is how the lesson sticks.
Practice
Problems to solve in your own notebook. Each states the problem, not the steps: working out the steps is the exercise. Level A applies the lesson, B combines it with earlier ones, C stretches it.
The self-checking notebook for this lesson is Notebook 2 · Binary Search.
Common mistakes
What you will see when it goes wrong, why it happens, and the fix.
Where it’s used
Where this lesson’s ideas turn up in real work.