Phase 4: Computational Thinking & Algorithms · ~40 minutes · Python · uv

Searching — Slow vs. Fast

Binary search on unsorted data doesn't just get slower. It can return a confidently wrong answer and never tell you.

Hiring signal: Knows binary search's precondition isn't optional, and can explain why 'it worked once' doesn't prove it's correct

What you will learn

Implement linear search and binary search, and explain how binary search eliminates half the remaining space each step
Measure real timing differences between them as input size grows
Explain why binary search requires sorted data as a hard precondition, not a suggestion
Predict roughly how many comparisons binary search needs for a given list size

Introduction

Type: Learn Languages: Python Prerequisites: Phase 03 (Data & Statistical Literacy) Time: ~40 minutes

Objective

Learning objectives

Implement linear search and binary search, and explain how binary search eliminates half the remaining space each step
Measure real timing differences between them as input size grows
Explain why binary search requires sorted data as a hard precondition, not a suggestion
Predict roughly how many comparisons binary search needs for a given list size

What you're building

A script (search_comparison.py) that:

Implements both linear_search and binary_search as shown above
Times both at n = 10, 10_000, and 1_000_000, using time.perf_counter(), and prints the results
Verifies both functions agree with each other (and with Python's own logic) on at least 3 different target values, including one not present in the data
Reproduces this lesson's unsorted-data bug: runs binary_search on a shuffled version of the same data, showing at least one case where it returns a wrong answer, with a comment explaining exactly why

A sorted list has 1,000 items. Roughly how many comparisons will binary search need in the worst case?

Binary search roughly needs log base 2 of the list size. 2^10 = 1024, which is just over 1,000 — so about 10 comparisons, not 500 and nowhere near 1,000. This is the entire point of this lesson's timing results: doubling or even multiplying the data by 100x barely changes binary search's comparison count, which is exactly why its timing barely moved between 10,000 and 1,000,000 items above.

Unlock the full lesson

You've read the first 2 sections. The rest of this lesson covers The Problem, Check Yourself, Key Terms & Next — plus a hands-on lab, quiz, and project artifact.

Create a free account to unlock Phase 0 and Phase 1 of every course — no credit card.