Searching Algorithms

Overview

Searching means locating a target value within a collection. Linear search checks each element in order and works on any list in O(n) time. Binary search repeatedly halves a sorted list to find the target in O(log n) time, making it far faster on large sorted data.

Syntax / Usage

Linear search scans left to right; binary search needs a sorted list and compares against the middle element to discard half the range each step.

def linear_search(items, target):
    for index, value in enumerate(items):  # O(n) time
        if value == target:
            return index
    return -1

def binary_search(items, target):          # O(log n) time, list must be sorted
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Examples

Linear search works even on unsorted data:

names = ["ada", "grace", "linus"]
print(linear_search(names, "grace"))  # 1

Binary search finds an index quickly in a sorted list of numbers:

numbers = [1, 3, 5, 7, 9, 11]
print(binary_search(numbers, 7))   # 3
print(binary_search(numbers, 8))   # -1 (not present)

Common Mistakes

• Running binary search on an unsorted list, which returns wrong results.
• Off-by-one errors with low, high, and mid boundaries.
• Using low < high instead of low <= high, missing the final element.
• Recomputing len(items) inside the loop instead of once up front.
• Forgetting that O(n) linear search can beat binary search for very small lists.

See Also

algorithms-big-o-notation algorithms-sorting algorithms-two-pointers