Linear and Binary Search

Definition

How do you find a word in a dictionary without reading every page?

Linear search checks items one by one from the start until it finds the target or reaches the end; it works on any list. Binary search works only on a sorted list: it compares the target with the middle item and throws away the half that can't contain it, repeating until it is found or nothing is left.

In simple words

Looking for a friend in a messy crowd, you check face by face: that's linear search. Looking up 'mango' in a dictionary, you open the middle, see 'kite', and know mango is in the second half. Each look halves what's left, so even a 1,000-page dictionary takes about ten looks.

Why it matters

Searching is everywhere: finding a user, a word, a file. Binary search shows how a smarter method beats a faster computer, an idea that runs through all of algorithm design and AI.

How it works

low ← 0, high ← last index
while low ≤ high:
    mid ← (low + high) // 2
    if items[mid] = target: found
    if items[mid] < target: low ← mid + 1
    else: high ← mid − 1
not found

List size	Linear search, worst case	Binary search, worst case
10	10 checks	4 checks
1,000	1,000 checks	10 checks
1,000,000	1,000,000 checks	20 checks

In code

Both searches, each counting how many items it checks.

searching.py

def linear_search(items, target):
    checks = 0
    for index, item in enumerate(items):
        checks += 1
        if item == target:
            return index, checks
    return -1, checks

def binary_search(items, target):
    low, high, checks = 0, len(items) - 1, 0
    while low <= high:
        mid = (low + high) // 2
        checks += 1
        if items[mid] == target:
            return mid, checks
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, checks

names = sorted(["Zoya", "Aarav", "Meera", "Kabir", "Sana", "Ishaan", "Diya", "Rohan"])
print(names)
print("Linear search for Sana:", linear_search(names, "Sana"))
print("Binary search for Sana:", binary_search(names, "Sana"))

numbers = list(range(1, 1001))
print("Linear, 1000 items, target 999:", linear_search(numbers, 999)[1], "checks")
print("Binary, 1000 items, target 999:", binary_search(numbers, 999)[1], "checks")

Output

['Aarav', 'Diya', 'Ishaan', 'Kabir', 'Meera', 'Rohan', 'Sana', 'Zoya']
Linear search for Sana: (6, 7)
Binary search for Sana: (6, 3)
Linear, 1000 items, target 999: 999 checks
Binary, 1000 items, target 999: 9 checks

Try it yourself

Binary search, step by step

Search for 23 in [3, 8, 12, 17, 23, 31, 40]. Put the steps in order.

1Look at 23. It matches, so the search is over after 3 checks.
2Look at the middle of what's left, 31. 23 is smaller, so keep the left part: [23].
3Look at the middle item, 17. 23 is bigger, so keep the right half: [23, 31, 40].

Common mistakes

Running binary search on an unsorted list. It gives wrong answers.
Getting the boundaries wrong and looping forever. Move low to mid + 1 and high to mid − 1.
Sorting a list just to search it once. Sorting costs more than one linear search.

Check yourself

1. Binary search needs the list to be…

2. Roughly how many checks does binary search need for 1,000 items?

3. When is linear search the right choice?

Summary

Linear search checks items one by one; it works on any list.
Binary search halves a sorted list each step.
For a million items: up to a million checks against about twenty.

Finished reading?

Sources: W3Schools DSA: Binary Search · W3Schools DSA with Python