Linear vs Binary Search: Animated Python Tutorial

Section 01

The Lost Letter — A Story About Searching

📖 Real World Analogy

Two Ways to Find One Page

You drop a 1,000-page book and the pages scatter. You need page 487.

Friend A picks up pages one at a time, reads each number, and keeps going until they hit 487. If they're unlucky, that's 1,000 checks.

Friend B first stacks the pages in order, opens to the middle, sees “500 — too high”, throws away the top half, opens the middle of what's left, and repeats. Friend B finds page 487 in about 10 checks.

Friend A is Linear Search. Friend B is Binary Search. Same goal, wildly different effort — and the difference is the whole point of this lesson.

🔎

The Core Insight

Searching is everywhere: looking up a contact, finding a record in a database, hitting Ctrl‑F. The smartest algorithm depends on one question: is your data already sorted? If not, linear search is your tool. If yes, binary search is dramatically faster.

Section 02

Linear Search — What It Is & Where It Shines

Linear Search (also called sequential search) is the most intuitive search there is: start at the first element, compare it to your target, and walk forward one element at a time until you either find a match or run off the end of the list. It makes no assumptions about the data — the list can be in any order at all.

🎲

Works on Unsorted Data

No sorting required

This is its superpower. Sorting first costs time. If the data is messy, scattered, or arrives in random order, linear search just works — no setup.

🧩

Dead Simple

~3 lines of logic

A loop and a comparison. Almost impossible to get wrong, easy to read, and the first algorithm every programmer learns. Great for teaching and quick scripts.

⚡

Best for Small Lists

n < ~100

When the list is tiny, the speed difference vanishes. The overhead of sorting for binary search isn't worth it. Linear search wins on simplicity.

✅ Ideal Use Cases for Linear Search

Case 1

Unsorted collections — a shuffled deck, raw log lines, freshly scraped data. Sorting would cost more than just scanning once.

Case 2

Small datasets — searching a dropdown of 20 countries or a to‑do list. The list is so short that speed is irrelevant.

Case 3

Find‑all / linked structures — when you must visit every element anyway (e.g. count matches), or in a linked list where you can't jump to the middle.

Case 4

Data that changes constantly — if items are inserted and removed all the time, keeping the list sorted is expensive, so scanning is simpler.

Section 03

Hands‑On: Watch Linear Search Run, Line by Line

Press Step to advance one operation at a time, or Auto‑Play to watch it run. The highlighted code line on the right is the exact line being executed, and the status bar explains what that line is doing right now. Try the different target chips — including one that's not in the list.

Array (unsorted)

Python — executing line

def linear_search(arr, target): for i in range(len(arr)): if arr[i] == target: return i return -1

Ready. Choose a target and press Step or Auto‑Play.

target:

💡

Notice the Pattern

Every element you pass turns faded — it has been checked and ruled out. For target 99 (last element) linear search must touch every cell. For a missing target like 77 it scans the whole list and returns -1. That worst‑case “check everything” behaviour is exactly what makes it O(n).

Section 04

What Each Line Is Doing

This table is the same mapping the animation uses — each code line and the task it performs.

📋 Linear Search — Line‑by‑Line

Line 1

def linear_search(arr, target): — defines the function: arr is the list to search, target is the value we want.

Line 2

for i in range(len(arr)): — walk an index i from 0 to the end, visiting every element once, left to right.

Line 3

if arr[i] == target: — the comparison. Ask: “is the element at position i the one I'm looking for?”

Line 4

return i — match found! Hand back the index immediately and stop searching.

Line 5

return -1 — the loop finished with no match, so report “not found” with the sentinel -1.

Section 05

The Full Python Code

def linear_search(arr, target):
    # Walk through every index, left to right
    for i in range(len(arr)):
        if arr[i] == target:   # compare current element with target
            return i        # found it -> return its position
    return -1               # scanned everything, not found


# --- Try it out ---
data = [42, 17, 8, 99, 23, 4, 56, 31]

print(linear_search(data, 23))   # 23 sits at index 4
print(linear_search(data, 77))   # 77 is missing

OUTPUT

4 -1

Section 06

Linear Search — Cost Summary

Scenario	Comparisons	Big‑O	Meaning
Best case	1	O(1)	Target is the very first element.
Average case	n / 2	O(n)	Target is somewhere in the middle.
Worst case	n	O(n)	Target is last, or not present at all.
Extra memory	—	O(1)	No extra space needed.
Data requirement	—	None	Works on sorted or unsorted data.

Section 07

Binary Search — The Power of Halving

📖 Story

The Number Guessing Game

“I'm thinking of a number between 1 and 100.” You guess 50. “Higher.” You guess 75. “Lower.” You guess 62… Each guess halves what's left. In at most 7 guesses you'll nail any number from 1 to 100. That “cut it in half every time” trick is precisely Binary Search — and it's why it scales to millions of items with ease.

Binary Search needs one thing in return for its speed: the data must be sorted. Given that, it looks at the middle element, decides whether the target is in the left half or the right half, and throws the other half away — every single step.

🚀

Blazingly Fast

O(log n)

1,000,000 items → at most ~20 checks. A billion items → ~30 checks. Doubling the data adds just one extra step. This is the headline benefit.

📊

Scales Effortlessly

huge datasets

Databases, search engines, and indexes lean on this. When data is large and lookups are frequent, the speed gap over linear search becomes enormous.

🎯

Beyond Plain Lookup

binary-search-on-answer

The halving idea powers more than array lookups: finding insertion points, square roots, version bisection (git bisect), and optimisation problems.

⚠️

The One Hard Rule

Binary search is only correct on sorted data. Run it on an unsorted list and it will confidently return the wrong answer. If your data isn't sorted and you only search once, sorting first (O(n log n)) may cost more than a single linear scan (O(n)) — so choose deliberately.

Section 08

Hands‑On: Watch Binary Search Halve the List

Same controls as before. Watch how the lo and hi pointers close in, the mid element lights up blue, and half the array greys out after every single comparison. Notice how few steps it takes compared with linear search above.

Array (sorted)

Python — executing line

def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1

Ready. Choose a target and press Step or Auto‑Play.

target:

Section 09

What Each Line Is Doing

📋 Binary Search — Line‑by‑Line

Line 1

def binary_search(arr, target): — defines the function. Remember: arr must already be sorted.

Line 2

lo, hi = 0, len(arr) - 1 — set the two boundaries: lo at the start, hi at the end. The search window is the whole array.

Line 3

while lo <= hi: — keep going as long as the window still has elements in it.

Line 4

mid = (lo + hi) // 2 — pick the middle index of the current window (integer division).

Line 5

if arr[mid] == target: — is the middle element the target? If yes…

Line 6

return mid — …found it. Return the middle index and stop.

Line 7

elif arr[mid] < target: — middle is too small, so the target must be to the right.

Line 8

lo = mid + 1 — discard the left half (everything up to and including mid).

Line 9

else: hi = mid - 1 — otherwise middle is too big; discard the right half and search left.

Line 10

return -1 — the window shrank to nothing, so the target isn't present.

Section 10

The Full Python Code

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1          # search window = whole array
    while lo <= hi:
        mid = (lo + hi) // 2           # middle of the window
        if arr[mid] == target:
            return mid                # found
        elif arr[mid] < target:
            lo = mid + 1             # go right
        else:
            hi = mid - 1             # go left
    return -1                        # not found


# --- Try it out (NOTE: list must be sorted) ---
data = [4, 8, 17, 23, 31, 42, 56, 99]

print(binary_search(data, 23))   # 23 sits at index 3
print(binary_search(data, 77))   # 77 is missing

OUTPUT

3 -1

🛠️

You Don't Have to Write It Yourself

Python ships with the bisect module — bisect.bisect_left(arr, target) gives you a production‑grade binary search for finding insertion points. Understand the mechanics first, then reach for the battle‑tested library in real code.

Section 11

Visual Diagram — How Binary Search Eliminates Half Each Time

Start with the whole sorted window

8 elements, lo = 0 and hi = 7. Looking for 23. Candidates remaining: 8.

Check the middle → 23 found early

mid = (0 + 7) // 2 = 3. arr[3] = 23. Match on the first probe! In the worst case, though, each probe instead halves the window.

If it had been too small → drop the left half

Set lo = mid + 1. Half the candidates vanish in one step. Remaining: 4.

Repeat the halving

Each loop cuts the window in half again: 8 → 4 → 2 → 1. That's log₂(8) = 3 steps maximum.

Window empties → report result

Return the found index, or -1 once lo passes hi. Done in O(log n) probes.

📐

Why log n? The Doubling Intuition

Ask: “how many times can I halve n before I reach 1?” That count is log₂(n). For n = 1,000,000 the answer is ~20. For n = 1,000,000,000 it's only ~30. Each doubling of the data adds just one step — that is the magic of logarithmic growth.

Section 12

Head‑to‑Head Comparison

Property	Linear Search	Binary Search
Data must be sorted?	No	Yes — mandatory
Time complexity (worst)	O(n)	O(log n)
Best case	O(1)	O(1)
Checks for 1,000,000 items	up to 1,000,000	~20
Extra memory	O(1)	O(1) iterative
Code complexity	Very simple	Easy to get off‑by‑one wrong
Works on linked lists?	Yes	No (needs random access)
Best when…	Small or unsorted data	Large, sorted, frequently searched data

🐌 Linear Search — worst case (n = 8)

Step	Checks element
1	index 0
2	index 1
…	…
8	index 7
Total	8 comparisons

🚀 Binary Search — worst case (n = 8)

Step	Window size
1	8 → 4
2	4 → 2
3	2 → 1
Total	3 comparisons

Section 13

Golden Rules

🎯 Searching — Rules of Thumb

Sorted → binary, unsorted → linear. This single question decides almost everything. Never run binary search on unsorted data — it silently returns wrong answers.

Tiny lists? Don't overthink it. For a few dozen elements, linear search's simplicity beats the setup cost and bug risk of binary search.

Search once vs. search often. If you'll search a dataset many times, sorting once (O(n log n)) then using binary search pays off hugely. For a single lookup on unsorted data, a linear scan is cheaper than sorting first.

Mind the off‑by‑one. The classic binary search bugs are the loop condition (lo <= hi, not <) and the updates (mid + 1 / mid - 1). Get these exactly right.

Use the standard library. Python's bisect, C++'s std::lower_bound, Java's Arrays.binarySearch — learn the mechanics, then trust the tested implementation in production.

Both use O(1) memory. Neither needs extra space (the iterative binary search above). If you write binary search recursively, watch the call‑stack depth.