Browser lab20 min+60 XP

Binary search

Halve the problem every step. Find one item in a million in about 20 checks.

0% done

Code runs right here in your browser. Nothing to install.

TASK 1

Learn it

Key idea

Binary search halves a sorted list each step.

Key words
binary_search(nums, 78)step 1: 34 < 78: keep the right half3low8 15 21 34mid42 57 63 78 91highstep 2: 63 < 78: keep the right half3 8 15 21 34 42low57 63mid78 91highstep 3: found at position 83 8 15 21 34 42 57 63 78low/mid91high
Searching a sorted list for 78. Faded numbers have been ruled out.

If a list is sorted, you can search much faster. Binary search looks at the middle item. If it is the target, done. If the target is smaller, throw away the right half; if bigger, throw away the left half. Repeat on the half that is left.

Each step halves the search area. A list of 1,000,000 items needs at most about 20 steps, because 2 to the power 20 is just over a million. Linear search might need a million.

You track the search area with two positions, low and high, and keep going while low <= high.

Real life linkIt is how you find a word in a paper dictionary: open near the middle, decide which half, and repeat.
Example code
def binary_search(items, target):
    low = 0
    high = len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        print("checking position", mid)
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [3, 8, 15, 21, 34, 42, 57, 63, 78, 91]
print("found at", binary_search(nums, 63))
TASK 2

Try it yourself

+10 XP

Count the steps. Change binary_search to return a tuple (position, steps). Search a sorted list of the numbers 0 to 999,999 for 777777 and print the result. It should take 20 steps or fewer.

Create a free account to start this lab

Sign in to write, run and check your code here. Your progress, XP and code are saved to your account. No card needed.

TASK 3

Capture the flag

+10 XP

What must be true about a list before you can use binary search on it?

Create a free account to start this lab

Sign in to answer the flag question. Your progress, XP and code are saved to your account. No card needed.

HOMEWORK

Higher or lower bot

+20 XP

The computer must guess a secret number between 1 and 100 using binary search. The test answers each guess with higher, lower or correct. Print each guess like Is it 50?, and finish with Got it in 3 guesses! (with the real count).

Create a free account to start this lab

Sign in to do this homework and have it checked. Your progress, XP and code are saved to your account. No card needed.