lesson 3.14.3 binary search

Implementing a 'Divide and Conquer' Search on a Sorted List

Imagine a zombie is chasing you. You have to find the antidote hidden in one of 100 lockers. If you check them one by one, you get eaten. If you check random lockers, you get eaten. But, if you use Binary SearchA search algorithm which can only be performed on an ordered (sorted) list and works by splitting the list in half and discarding the unwanted items until a search item is either found or not found., you can find that antidote in 7 checks or less, guaranteed. Today is about speed, efficiency, and how to find an antidote in a locker without getting eaten.

Learning Outcomes

The Building Blocks (Factual Knowledge)

Recall that a Binary Search works by repeatedly finding the midpointI have no idea what this means and discarding half the data.

State the absolute preconditionI have no idea what this means that data must be sortedI have no idea what this means for this algorithm to function.

Identify the standard variables required:

low

high

, and

mid

The Connections and Theories (Conceptual Knowledge)

Explain why Binary Search is fundamentally faster than Linear Search for large datasets (Logarithmic Efficiency).

Analyse why the search logic fails completely if the dataset is unordered.

Compare the worst-case scenario of 7 steps (for 100 items) against 100 steps for a linear approach.

The Skills and Methods (Procedural Outcomes)

Construct a `while` loop that runs as long as the search area is valid (`low <= high`).

Calculate the integer midpoint using floor division (`//`).

Implement conditional logic to update the `low` or `high` pointers based on the target value.

Digital Skill Focus: Accurate copying and pasting

The Need for Speed

Computers process billions of pieces of data in a fraction of a second. If Instagram checked every single user one-by-one to find your profile when you logged in (using a linear searchStarts at the beginning of the list and compares each element in turn with the required value until a match is found, or the end of the list is reached. Is the only option with an unordered list (though could be used for any list). strategy), you would be waiting for days. We need a faster way.

Binary SearchA search algorithm which can only be performed on an ordered (sorted) list and works by splitting the list in half and discarding the unwanted items until a search item is either found or not found. is a "Divide and Conquer" algorithm.

Instead of checking items sequentially (one-by-one), it jumps straight to the middle of the list. By comparing the middle item to what you are looking for, it can instantly throw away half of the list. The algorithm keeps halving the list until only one item remains.

Task 1 The Zombie Antidote

You are the developer for a zombie apocalypse survival robot. There are 100 lockers in the abandoned medical research centre (indexes 0-99). The zombie antidote is hidden in one of them but you don't know which. Your robot has a "Sniffer" sensor that tells you if the antidote is to the Left or Right of your current position.

Get Organised

Open up Thonny on your computer.

If it's the first time you've used Thonny today, you will get a blank script. If not, go ahead and create a new one.

Organise your workspace.

Import some cool things

Let's tell Python we want to use some of its built-in tools. Firstly we will ask python to give us access to all its random number generation functions by importing the random library. We'll use this to choose a random locker to place the antidote in. Then we will ask Python to allow us to use its functions in the time library. We'll use this to make our simulation seem a little more realistic by pausing after each locker inspection.

import random
import time

Let's get set up

Now, let's build our lockers and choose a random locker to place the antidote in.

length = int(input("How many lockers are there (try 100)? "))
lockers = ["Empty"] * length
location = random.randint(0, length - 1)
lockers[location] = "Antidote"

Wait for it...

When you are building simulations in Python it's useful to give the user a little control over when the simulations should start. So we use this simple trick to pause the script until the user presses the enter key.

input("\nPress ENTER to try a Linear Search...\n")

Search linearly

I know this lesson is about binary search but let's step back and run a linear search on the lockers to see how long it would take to find the antidote. This will allow us to compare the efficiency of these two search strategies (so we can see if the zombie will catch us).

linear_tries = 0
for i in range(length):
    linear_tries = linear_tries + 1
    print(f"Try {linear_tries}: Checking locker {i+1}...")
    
    if lockers[i] == "Antidote":
        print(f"FOUND IT! The antidote was in locker {i+1}.")
        break
    else:
        print(" Not here. Move on...")
    time.sleep(0.1)

Wait for it...

Again, it's important we give the user a little control so we pause here until they press enter.

input("\nPress ENTER to try a Binary Search...\n")

Search binarily

Now let's implement a binary search. To enable this to work correctly we need to implement a sniffer which will tell us whether the antidote is in a lower numbered or higher numbered locker than the one we have just opened.

binary_tries = 0
low = 0
high = length - 1
while low <= high:
    binary_tries = binary_tries + 1
    mid = (low + high) // 2
    print(f"Try {binary_tries}: Sniffer checks the middle locker ({mid+1})...")
    if lockers[mid] == "Antidote":
        print(f"FOUND IT! The antidote was in locker {mid+1}.")
        break
    else:
        if mid < location:
            print(" Sniffer says: GO RIGHT (Higher)")
            low = mid + 1
        else:
            print(" Sniffer says: GO LEFT (Lower)")
            high = mid - 1
    time.sleep(0.1)

Wait for it...

Ok. We've found the antidote using two different search strategies so let's show the user some statistics but only when they are ready.

input("\nPress ENTER for the statistics...\n")

Let's look at the stats

The statistics speak for themselves.

print(f"The linear search took {linear_tries} tries to find the antidote.")
print(f"The binary search took {binary_tries} tries to find the antidote.")

Of course there is a small chance that the linear search would find the antidote in less than seven steps but only if it was in one of the first seven lockers. The binary search guarantees will find it in seven, so it's way more efficient in by far the majority of cases.

Surely this is a fluke?

Nope. Why don't you try running it again...

Try 200 lockers

Try 1000 lockers

Try 10000 lockers

Try 100000 lockers

The truth is that, if during the time taken to search the first 10 lockers, the zombie had caught up with you, there is only one guarenteed method of survival.

Outcome: You didn't get eaten by a zombie because you used the binary search algorithm to find the antidote.

The Fatal Flaw

Binary Search is powerful, but it is fragile. It has one major weakness.

Imagine trying to use the "Higher or Lower" strategy in a library where a mischievous student has thrown all the books on the floor in a random pile. You pick up a book from the middle of the pile. It's "Harry Potter". You are looking for "The Hobbit". You know "The Hobbit" comes after "Harry Potter" alphabetically. But which half of the pile do you throw away? You can't know. Because the books aren't in order, "The Hobbit" could be anywhere. The logic collapses.

Task 2 The Impossible Search

Computers don't have common sense. They only follow rules. In this activity, you will see what happens when you force a computer to use Binary Search on a messy list.

Get Organised!

Get into pairs. You need one set of playing cards (Ace to King).

Decide who is the Dealer and who is the Searcher.

The Trap (Unsorted)

Dealer: Shuffle the cards and lay them out face down in a straight line.
Searcher: Your target is the 7. You must follow these robot rules EXACTLY:

Point to the middle card. Dealer flips it.

Is it the 7? If yes, you win!

If it is smaller than 7, you MUST discard the left pile (because 7 should be on the right).

If it is bigger than 7, you MUST discard the right pile.

Did you find it? or did you accidentally throw the 7 in the bin?

The Fix (Sorted)

Dealer: Sort the cards in order (Ace, 2, 3... King) and lay them face down.
Searcher: Try the exact same search again.

Outcome: Understanding that sorting is a critical preconditionI have no idea what this means for Binary Search.

Today you have learnt that Binary SearchA search algorithm which can only be performed on an ordered (sorted) list and works by splitting the list in half and discarding the unwanted items until a search item is either found or not found. is an incredibly fast way to find data by repeatedly halving the search area, but it relies on the strict preconditionI have no idea what this means that the data must be sortedI have no idea what this means first (or we use a zombie antidote sniffer).