← Back to course
Code Crew G5 / Week 07 / Wednesday
3/6
Week 07 · Binary search

Wednesday

The binary search code
// Cut it in half
⏱ about 15 min

Wednesday: The binary search code

Rocket wants the halving search built into the catalog panel. He types fast and stops at two lines.

"When the target is bigger, I move low," he says. "But to where? To mid?"

Raven points at the middle spot. "What do you notice about mid after we check it?"

"It is not the target, so we never need it again!" Rocket says.

Nova blinks. "Here is a hint. Move one spot past mid, in the right direction."

Binary search in Python

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

ids = [3, 8, 12, 15, 21, 27, 30, 36]
print(binary_search(ids, 27))
print(binary_search(ids, 10))
Output:
5
-1
  • If the middle item matches, return its spot.
  • If the middle item is too small, the target is to the right. low = mid + 1.
  • If the middle item is too big, the target is to the left. high = mid - 1.
  • When low passes high, no spots are left. Return -1 for not found.
def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = ____
        else:
            high = ____
    return -1

print(binary_search([3, 8, 12, 15, 21, 27, 30, 36], 30))
First blank: low = ?
Second blank: high = ?
THINK ABOUT THE SEARCH FOR 10.
  • Read the question.
  • Tap your answer.
Why does binary_search(ids, 10) return -1?
What does binary_search(ids, 36) return?

Practice lab: three searches

def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

ids = [4, 9, 13, 18, 22]
print(binary_search(ids, 4))
print(binary_search(ids, 22))
print(binary_search(ids, 5))
What does the first print line show?
What does the second print line show?
What does the third print line show?
What is high at the start?
CODE CHECK
  • Read the question.
  • Tap your answer.
Searching for 5, the item at mid is 9. Which line runs?
When does the while loop stop without finding the target?
Why is it low = mid + 1 and not low = mid?
StatementTrue or false?
The first mid for ids is spot 2.?
binary_search returns the target itself.?
Searching for 4 checks spot 2, then spot 0.?
return -1 runs when low passes high.?
WHY THIS EXERCISETracing low, high and mid shows exactly how the search moves.
What does binary_search(ids, 18) return?
WHY THIS EXERCISE18 sits in spot 3, found on the second check.

Great reading! Binary search is short, but every line matters. Tomorrow we count its checks on bigger lists.

← Tuesday