Binary Search Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes the whole module on data such as order amounts, readings and parcels. Decide first what the question is asking for, then pick the template that fits.
Exact value, boundary or count
A sorted list and the words "first", "last", "how many" or "between" point to boundary searches. A single yes or no about one value is the classic loop or one bisect check.
from bisect import bisect_left, bisect_right
amounts = [40, 90, 90, 120, 250, 250, 250, 400, 650]print(bisect_left(amounts, 250), bisect_right(amounts, 250))print(bisect_right(amounts, 399) - bisect_left(amounts, 100))4 7 4
Example 1 · Orders per price band
from bisect import bisect_left, bisect_right
amounts = [40, 90, 90, 120, 250, 250, 250, 400, 650]bands = [(0, 99), (100, 299), (300, 999)]for low, high in bands: count = bisect_right(amounts, high) - bisect_left(amounts, low) print(f"{low}-{high}: {count}")0-99: 3 100-299: 4 300-999: 2
What this code does
- Each band needs two O(log n) searches, so the report costs O(bands x log n) with no pass over the data.
- The list must be sorted. Both ends of a band are included.
The first line gives the run of 250s: positions 4 to 6. The second counts the values from 100 to 399.
Rotated or peak
If the list is two sorted runs, compare mid with an end and keep the half that must hold the answer. If it only rises and falls, move toward the higher neighbour.
def find_min(items): lo, hi = 0, len(items) - 1 while lo < hi: mid = (lo + hi) // 2 if items[mid] > items[hi]: lo = mid + 1 else: hi = mid return lo
readings = [61, 70, 75, 20, 28, 35, 44]print(find_min(readings))3
Example 2 · Highest reading of a wrapped log
def find_min(items): lo, hi = 0, len(items) - 1 while lo < hi: mid = (lo + hi) // 2 if items[mid] > items[hi]: lo = mid + 1 else: hi = mid return lo
readings = [61, 70, 75, 20, 28, 35, 44]start = find_min(readings)print("sorted order starts at", start, "and the highest reading is", readings[start - 1])sorted order starts at 3 and the highest reading is 75
What this code does
- The log wrapped around, so it is a rotated sorted list. The smallest item is where the sorted order starts.
- The item just before it is the largest. If start is 0, readings[-1] is the last item, which is the largest, so the code still works.
The smallest reading is at position 3, so the sorted order starts there and the highest reading is just before it.
Search the answer
If there is no list but a number to choose, and a check says whether a number is big enough, binary search the numbers. The cost is the check times log of the range.
def first_true(lo, hi, ok): while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return lo
print(first_true(1, 40, lambda x: x * x >= 300))18
Example 3 · Split into parts with the smallest largest sum
def pieces_needed(items, limit): pieces, total = 1, 0 for value in items: if total + value > limit: pieces += 1 total = 0 total += value return pieces
def first_true(lo, hi, ok): while lo < hi: mid = (lo + hi) // 2 if ok(mid): hi = mid else: lo = mid + 1 return lo
items = [7, 2, 5, 10, 8]parts = 2print(first_true(max(items), sum(items), lambda limit: pieces_needed(items, limit) <= parts))18
What this code does
- The answer is the smallest limit for which the items can be cut into at most 2 pieces, each with a total not above the limit.
- A bigger limit never needs more pieces, so the check is monotonic. Cost is O(n log(sum)).
Any monotonic yes or no check fits this template: only the check and the bounds change.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
Write binary_search with the closed-window loop and print the position of 63 in [4, 9, 15, 22, 31, 47, 58, 63, 71, 90].
7
Exercise 2· Easy
Marks are [35, 48, 52, 60, 71, 85, 92]. Print how many students scored at least 60, using one bisect call.
4
Exercise 3· Medium
Print the first and last position of 10 in [5, 10, 10, 10, 20, 30] on one line, separated by a space.
1 3
Exercise 4· Medium
A sorted list was rotated into [40, 50, 60, 5, 10, 20, 30]. Print its smallest value with a binary search.
5
Exercise 5· Medium
Search [40, 50, 60, 5, 10, 20, 30] for 5 and for 55 with a rotated binary search and print both positions.
3 -1
Exercise 6· Hard
Print the value of a peak in [1, 4, 9, 6, 2] found with binary search.
9
Exercise 7· Hard
Piles are [5, 8, 12, 20] and 6 hours are allowed. Print the smallest whole speed that clears them in time.
10
Exercise 8· Hard
Without math.isqrt, print the integer square root of 1000000000001 with a binary search.
1000000
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Binary Search