Search Algorithms

Finding a name in a phone book by reading every entry from page one works, eventually. Opening to the middle and throwing away the wrong half each time works a few hundred times faster. Today you'll work both directions of the algorithm street: extract an algorithm from search code you're given, and build search code from an algorithm you're given.

Overview

You'll write the natural-language algorithm for linear search by reading its code, then implement binary search in Python by following its algorithm. Same two skills as the last two labs — extraction and implementation — applied to the two classic ways of finding things.

Builds on: Algorithm Extraction — extracting an algorithm from code, now paired with its opposite.

You've got it when…

Your linear search algorithm accurately describes what the code does, in plain English.
Your binary search program follows the given algorithm and finds a target in a sorted list.
Your program reports when the target is not in the list.
You've tested it: first item, last item, middle item, missing item.

Collaboration & AI

Work: On your own. Compare algorithms with a neighbor after you've each written one.

AI — AIAS Level 1, No AI: Translating between code and algorithm — both directions — is the skill being built. Do the translating yourself. What the levels mean.

Linear Search

This code searches for a target number in a list of numbers.

numbers = [12, 7, 25, 3, 18, 42, 9]
target = 18

for i in range(len(numbers)):
    if numbers[i] == target:
        print("Found at index", i)

Write the algorithm for this code in your notebook. Natural language, numbered steps — precise enough that someone who has never seen the code could rewrite it.

Why 'linear'?

Linear search checks every item, one at a time, front to back. The time it takes grows in a straight line with the length of the list — double the list, double the work. It's the only option when the list is in no particular order.

Binary Search

This is the algorithm for binary search.

Start with a sorted list of values.
Set low to the first index of the list.
Set high to the last index of the list.
Repeat the following steps while low is less than or equal to high:
1. Find the middle index: set middle to (low + high) // 2.
2. Compare the middle value to the target:
  1. If the middle value equals the target: report the index and stop.
  2. If the target is less than the middle value: move the search to the left half — set high to middle - 1.
  3. If the target is greater than the middle value: move the search to the right half — set low to middle + 1.
If the loop ends and the target was not found: report that the target is not in the list.
Write and test a Python program that implements this algorithm.

Warning

Step 1 of the algorithm is not decoration. Binary search only works on a sorted list — the whole trick is knowing which half to throw away, and an unsorted list gives you no way to know. Test your program with a sorted list.

Stuck? Open for a hint.

The algorithm's step 4 is a while loop, and steps 4.1–4.2 live inside it. Notice that the algorithm stops when it reports success — in Python, break (or returning from a function) does that job.

Turn It In

Your linear search algorithm, in your notebook.
Your binary search Python (.py) file, run and tested before you submit it.

How It's Graded

This lab is worth up to 4 points. One score covers everything you turn in.

Score	What it looks like
4 — Excellent	Your linear search algorithm accurately describes the code in numbered plain-English steps, and your binary search program follows the given algorithm, reports a missing target, and shows evidence of all four tests: first item, last item, middle item, missing item.
3 — Above Average	Both halves complete and working, with a minor slip — a missing-target report that never prints, or a test case skipped.
2 — Average	One direction done — the extraction or the implementation — but not both.
1 — Below Average	A linear algorithm that doesn't match the code and a binary search that can't find anything.
0 — Failing	Nothing in the notebook and no program.