Binary search

Python · Unit 23: Searching and sorting

If the list already comes sorted, looking one by one wastes that order. Look at the middle one: that is where you decide.

If your value is bigger than that one, everything to its left is useless. One glance throws away half the list.

nums = [2, 5, 8, 11, 14]
m = len(nums) // 2
print(nums[m])
print(nums[m + 1:])

Prints

8
[11, 14]

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Multiple choice
In [1, 4, 7, 9, 12] you are looking for the 12. You check the middle one, the 7. What can you throw away?
2. Predict the output
This version prints every number it looks at. What does it print?
3. Complete the code
Complete the midpoint between the two ends.
4. Find the bug
binary should return the position of the 8, which is 3, but it prints -1. Which line has the error?
5. Predict the output
The counter goes up on every round of the while. What does it print?
6. Multiple choice
What happens if you hand binary search a list that is not sorted?
7. Predict the output
What does this code print?
8. Complete the code
Complete it so it says whether the value is in the sorted list.
9. Find the case that fails
contains(nums, v) should return True if v is in the sorted list and False if it is not, including when v is bigger than all of them. Which call breaks it?

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.