I1 · Python Programming for AI

Linear and Binary Search

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.

12 min Intermediate · Sublevel Beginner Jump to the activity

What you need: The earlier topics of this module.

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.

Overview

  • Searching means finding whether a value is in a collection and, if so, where.
  • Linear search checks items one by one and works on any list, sorted or not.
  • Binary search halves a sorted list at each step, so it needs at most about log₂ n checks.
  • For 1,000,000 sorted items, linear search may need 1,000,000 checks; binary search needs about 20.
  • Python's in, list.index() and the bisect module provide ready-made searches.
  • Hash-based lookups in sets and dictionaries take about the same time however large the data.

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.

Key terms

Linear search
Checking items one by one until the target is found.
Binary search
Repeatedly halving a sorted list to find a target.
Target
The value being searched for.
Precondition
Something that must be true before an algorithm can work, such as a sorted list for binary search.
Midpoint
The middle position checked at each step of binary search.
Logarithmic time
Work that grows very slowly, adding one step each time the input doubles: O(log n).

Types

There are several searching methods, each suited to a different kind of data. These five are the most important.

1. Linear (sequential) search

Checking each item from the start until the target is found or the list ends.

  • How it works: Compare the target with item 0, 1, 2 and so on; return the index when they match, or -1 at the end; time O(n).
  • Example: Finding a friend's name in an unsorted attendance list.
  • When to use it: Use it for small or unsorted lists, or when you search only once.

2. Binary search

Repeatedly halving a sorted list by comparing the target with the middle item.

  • How it works: Keep low and high indexes; check mid = (low + high) // 2; if the target is smaller, search the left half, otherwise the right; time O(log n).
  • Example: Finding a word in a dictionary book by opening it in the middle and moving left or right.
  • When to use it: Use it on sorted data that you search many times; the bisect module does it for you.

3. Jump search

Jumping ahead in fixed blocks through a sorted list, then searching linearly inside one block.

  • How it works: With block size about √n, jump until an item exceeds the target, then step back through that block; time O(√n).
  • Example: In 10,000 sorted records, jump 100 at a time, then check at most 100 records.
  • When to use it: Use it when jumping forward is cheap but going backwards is costly, as on some storage media.

4. Interpolation search

Guessing where the target probably is from its value, like opening a phone book near "S" for Sharma.

  • How it works: It estimates the position as low + (target − a[low]) × (high − low) ÷ (a[high] − a[low]); on evenly spread data it averages O(log log n) checks.
  • Example: Looking up roll number 7,500 among roll numbers 1 to 10,000 starts near three-quarters of the way through.
  • When to use it: Use it on large, sorted, evenly distributed numeric data; it is slow on skewed data.

5. Hash-based lookup

Finding a value by computing where it is stored from the value itself, as sets and dictionaries do.

  • How it works: A hash function turns the key into a bucket number, so a lookup goes almost straight to the right place; average time O(1).
  • Example: "Pune" in visited_cities, where visited_cities is a set of 10,000 names.
  • When to use it: Use it when you look up items by exact key many times; it cannot find ranges or nearest values.

Explained in detail

Linear search: simple and universal

Linear search starts at the beginning and checks every item until it finds the target or reaches the end. It works on any list, sorted or not, and for short lists it is perfectly good. Its weakness is scale: in the worst case, when the target is last or absent, it checks every item, so a list ten times longer takes ten times longer. Python's in operator and the index() method use linear search on lists.

Binary search: the dictionary method

When you look up a word in a printed dictionary, you do not start at page one. You open near the middle, see whether your word comes before or after, and repeat in the half that remains. Binary search does exactly this. It keeps two markers, low and high, around the part of the list that could still contain the target. It checks the middle item: if it is the target, done; if the target is smaller, move high to just before the middle; if larger, move low to just after it. Each check throws away half of what is left.

How big the difference is

List sizeLinear search, worst caseBinary search, worst case
1010 checks4 checks
1,0001,000 checks10 checks
1,000,0001,000,000 checks20 checks
1,000,000,0001,000,000,000 checks30 checks

Doubling the list adds just one step to binary search. That is logarithmic growth, written O(log n), compared with O(n) for linear search. The catch is the precondition: the list must be sorted. Sorting costs time, so binary search pays off when you sort once and search many times, as databases and search indexes do.

Getting binary search right

  • Binary search is famous for subtle bugs. The computer scientist Jon Bentley reported in the 1980s that most professional programmers he tested got it wrong on the first try.
  • Use while low <= high, not <, or you may miss the last remaining item.
  • Always move low to mid + 1 or high to mid - 1; leaving them at mid can loop forever.
  • Test with the target at the start, middle, end, and absent, and with lists of length 0, 1 and 2.
  • In practice, Python's bisect module provides a tested binary search.

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 sizeLinear search, worst caseBinary search, worst case
1010 checks4 checks
1,0001,000 checks10 checks
1,000,0001,000,000 checks20 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.

  1. 1Look at 23. It matches, so the search is over after 3 checks.
  2. 2Look at the middle of what's left, 31. 23 is smaller, so keep the left part: [23].
  3. 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

Question 1

1. Binary search needs the list to be…

Question 2

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

Question 3

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