Unit 11.3A · Term 3

Algorithms: Linear & Binary Search

Searching is one of the most fundamental operations in computing. Linear search checks every element one by one. Binary search uses a "divide and conquer" strategy on sorted data to find items dramatically faster.

Learning Objectives

11.3.4.1 Implement linear search
11.3.4.2 Implement binary search

Lesson Presentation

11.3A-lesson-20-algorithms.pdf · Slides for classroom use

View Download

Conceptual Anchor

The Phone Book Analogy

Linear search = flipping through a phone book page by page from start to finish. Works for any book, but slow.
Binary search = opening the phone book to the middle, checking if name is before or after, then repeating with the correct half. Much faster, but the book must be alphabetized.

Rules & Theory

Linear Search

def linear_search(lst, target):
    """Search for target in list. Return index or -1."""
    for i in range(len(lst)):
        if lst[i] == target:
            return i    # Found! Return the index
    return -1           # Not found

# Example
numbers = [4, 7, 2, 9, 1, 5, 8]
result = linear_search(numbers, 9)
print(result)   # 3 (index of 9)

result = linear_search(numbers, 6)
print(result)   # -1 (not found)

Binary Search

def binary_search(lst, target):
    """Search SORTED list for target. Return index or -1."""
    low = 0
    high = len(lst) - 1

    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid          # Found!
        elif lst[mid] < target:
            low = mid + 1       # Search right half
        else:
            high = mid - 1      # Search left half

    return -1                   # Not found

# MUST be sorted!
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
result = binary_search(numbers, 11)
print(result)   # 5

Comparison

Feature	Linear Search	Binary Search
Data requirement	Any list (sorted or not)	Must be sorted!
Best case	1 comparison (first element)	1 comparison (middle element)
Worst case	n comparisons	log₂(n) comparisons
100 elements	Up to 100 checks	At most 7 checks
1,000,000 elements	Up to 1,000,000 checks	At most 20 checks!
Complexity	O(n)	O(log n)

Why log₂?

Binary search halves the remaining items each step. For 1024 items: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. That's 10 steps = log₂(1024). Incredibly efficient!

Worked Examples

1 Binary Search Trace

# List: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
# Target: 23

# Step 1: low=0, high=9, mid=4 → lst[4]=16 < 23 → low=5
# Step 2: low=5, high=9, mid=7 → lst[7]=56 > 23 → high=6
# Step 3: low=5, high=6, mid=5 → lst[5]=23 == 23 → FOUND at index 5!

# Only 3 comparisons for a list of 10 items!

Step	low	high	mid	lst[mid]	Action
1	0	9	4	16	16 < 23 → low = 5
2	5	9	7	56	56 > 23 → high = 6
3	5	6	5	23	23 == 23 → Found!

2 Linear Search — Count Occurrences

def find_all(lst, target):
    """Find ALL positions of target in list."""
    positions = []
    for i in range(len(lst)):
        if lst[i] == target:
            positions.append(i)
    return positions

data = [3, 7, 3, 2, 3, 8, 3]
result = find_all(data, 3)
print(f"Found at positions: {result}")  # [0, 2, 4, 6]
print(f"Occurrences: {len(result)}")    # 4

3 Search with Step Counter

def linear_search_counted(lst, target):
    steps = 0
    for i in range(len(lst)):
        steps += 1
        if lst[i] == target:
            return i, steps
    return -1, steps

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

# Compare efficiency
import random
data = sorted(random.sample(range(10000), 1000))
target = data[750]

idx1, steps1 = linear_search_counted(data, target)
idx2, steps2 = binary_search_counted(data, target)
print(f"Linear: found at {idx1}, {steps1} steps")   # ~751 steps
print(f"Binary: found at {idx2}, {steps2} steps")    # ~10 steps

Pitfalls & Common Errors

Binary Search on Unsorted Data

Binary search requires sorted data. Using it on an unsorted list gives wrong results or misses existing elements. Always sort first!

Off-by-One: low <= high

The while loop condition must be <= not <. With just <, you miss the case where the target is the last remaining element (when low == high).

Integer Division for mid

Use // for mid calculation: mid = (low + high) // 2. Using / gives a float, which can't be used as an index.

Pro-Tips for Exams

Search Tips

For exam trace tables: show low, high, mid, and lst[mid] at each step
Maximum comparisons for binary search = ⌈log₂(n)⌉ + 1
If the data is unsorted and you need one search → linear search
If you'll search many times → sort once, then use binary search
Python's in keyword does a linear search internally

Graded Tasks

Remember

What is the key requirement for binary search? What is the time complexity of each algorithm?

Understand

Why is binary search O(log n) while linear search is O(n)? Explain in your own words.

Apply

Trace binary search on [1, 3, 5, 7, 9, 11, 13] searching for 7. Show low, high, mid at each step.

Apply

Implement both linear and binary search, count the steps, and compare results for a list of 100 sorted numbers.

Analyze

A sorted list has 1024 items. What is the maximum number of comparisons binary search needs? What about linear search?

Create

Build a "number guessing game" that uses binary search strategy: the computer guesses your number in minimum steps.

Self-Check Quiz

1. Does binary search work on unsorted lists?

Click to reveal answer

2. How many comparisons does linear search need for a list of 1000 items (worst case)?

Click to reveal answer

3. How many comparisons does binary search need for 1000 items (worst case)?

Click to reveal answer

4. What does mid = (low + high) // 2 calculate?

Click to reveal answer

5. When should you use linear search instead of binary search?

Click to reveal answer