Binary search in Python

Tip: Choose Save as PDF in the print dialog to download. Use A4 paper size.

Binary search in Python

Name:
Date:
Class:
A

Quick Questions

Shade in the A or B circle for each question.

1. Which list can a binary search work on?
A [14, 2, 20, 5, 9] (unsorted)
B [2, 5, 9, 14, 20] (sorted)
2. Which line correctly keeps the binary search loop running?
A while low <= high:
B while low > high:
3. Which line correctly finds the middle index?
A mid = (low + high) // 2
B mid = (low + high) / 2
4. The item at mid is smaller than the target. What should the code do?
A low = mid + 1
B high = mid - 1
5. The item at mid is bigger than the target. What should the code do?
A low = mid + 1
B high = mid - 1
B

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left columnRight column
1mid = (low + high) // 2 AUsing < instead of <= means the loop stops before checking the last item when low equals high. It should be while low <= high:
2while low <= high: Blow never moves past mid, so the loop can get stuck forever on the same range. It should be low = mid + 1
3If the middle item is too small, ignore the left half by moving low up past mid Chigh = mid - 1
4If the middle item is too big, ignore the right half by moving high down below mid DKeeps looping while there is still a range of items left to search
5while low < high: EFinds the index of the middle item in the current search range
6low = mid Flow = mid + 1
C

Definitions

while low <= high:
D

Fill in the Blanks

Complete each line of code by filling in the missing parts.

1.
low = 0 ____ = len(nums) - 1 while low <= high:
2.
high = len(nums) - 1 while low __ high:
3.
while low <= high: mid = (low + high) __ 2
4.
mid = (low + high) // 2 if nums[mid] < target: low = ___ + 1
5.
nums = ______([9, 2, 7, 4]) low = 0
E

Spot the Error

Shade in the letter of the line that contains an error.

Question 1
A low = 0
B high = len(nums) - 1
C target = 7
D while low >= high:
E mid = (low + high) // 2
Question 2
A low = 1
B high = len(nums) - 1
C while low <= high:
D mid = (low + high) // 2
Question 3
A low = 0
B high = len(nums) - 1
C mid = (low + high) / 2
D print(nums[mid])
Question 4
A if nums[mid] == target:
B return mid
C elif nums[mid] < target:
D low = mid - 1
E else:
F high = mid - 1
Question 5
A nums = [12, 3, 25, 8, 16]
B nums.reverse()
C low = 0
D high = len(nums) - 1

Answer Key

Binary search in Python
Section A: Quick Questions
Q1
B — [2, 5, 9, 14, 20] (sorted)
Q2
A — while low <= high:
Q3
A — mid = (low + high) // 2
Q4
A — low = mid + 1
Q5
B — high = mid - 1
Section B: Match the Pairs
Q1
mid = (low + high) // 2 → Finds the index of the middle item in the current search range
Q2
while low <= high: → Keeps looping while there is still a range of items left to search
Q3
If the middle item is too small, ignore the left half by moving low up past mid → low = mid + 1
Q4
If the middle item is too big, ignore the right half by moving high down below mid → high = mid - 1
Q5
while low < high: → Using < instead of <= means the loop stops before checking the last item when low equals high. It should be while low <= high:
Q6
low = mid → low never moves past mid, so the loop can get stuck forever on the same range. It should be low = mid + 1
Section C: Definitions
Q1
while low <= high: — The binary search loop: while low <= high, check the middle item of a sorted list, then move low or high to halve the search range each time.
Section D: Fill in the Blanks
Q1
low = 0 high = len(nums) - 1 while low <= high:
Q2
high = len(nums) - 1 while low <= high:
Q3
while low <= high: mid = (low + high) // 2
Q4
mid = (low + high) // 2 if nums[mid] < target: low = mid + 1
Q5
nums = sorted([9, 2, 7, 4]) low = 0
Section E: Spot the Error
Q1
D — The loop must keep running while low is less than or equal to high. With >= the loop will not run properly. It should be while low <= high:
Q2
A — Binary search must start at the first index, which is 0. Starting low at 1 skips the first item in the list. It should be low = 0.
Q3
C — A single / gives a float like 2.5, which cannot be used as a list index. Use // for whole-number division: mid = (low + high) // 2.
Q4
D — If the middle item is smaller than the target, the target must be in the upper half, so low must move up. It should be low = mid + 1.
Q5
B — Binary search only works on a sorted list. reverse() just flips the order and does not sort it. It should be nums.sort().