Skip to content
Python Central Hub

Searching Visualized

Finding a value in a list sounds trivial — until the list has a million items. How you search matters enormously. This page contrasts the two classics: linear search, which checks every item, and binary search, which is dramatically faster but needs a sorted list.

What you’ll learn

  • how linear search scans one-by-one (works on any list)
  • how binary search halves the remaining range each step (needs sorted data)
  • why binary search is O(log n) — a million items in ~20 checks

Linear vs binary

search.py
def linear_search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i          # found it
    return -1                 # not present
 
def binary_search(nums, target):   # nums MUST be sorted
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1       # target is in the right half
        else:
            hi = mid - 1       # target is in the left half
    return -1
 
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))    # 5
search.py
def linear_search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i          # found it
    return -1                 # not present
 
def binary_search(nums, target):   # nums MUST be sorted
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1       # target is in the right half
        else:
            hi = mid - 1       # target is in the left half
    return -1
 
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(data, 23))    # 5

The blue range is what’s still in play; the yellow bar is the middle being checked. Each step throws away half the range. Click the canvas to pick a new target.

sketch Binary search halves the range p5.js
On a sorted list, binary search checks the middle and discards half the list each step. Click to search for a new target.

Linear search may check all n items; binary search checks about log₂ n. For 1,000,000 sorted items that’s the difference between up to a million comparisons and about 20. The catch: binary search only works if the list is already sorted.

Try it: Searching Exercises

Exercise 1 – Linear search

Exercise 2 – The binary search midpoint

Exercise 3 – Membership with in

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Was this page helpful?

Let us know how we did