Searching Algorithms in Python

Searching — finding whether and where an item appears — is one of the most fundamental tasks in programming and a favourite interview topic. The right algorithm can make the difference between checking a million items and checking twenty.

This lesson implements and compares linear search, binary search (iterative and recursive), jump search and interpolation search, explains their time complexity, and shows Python's built-in tools (in, index, bisect, sets and dicts).

Linear Search — O(n)

Check each element in turn until you find the target. It works on any list, sorted or not, and is the right choice for small or unsorted data. Python's in operator and list.index() perform linear searches.

Binary Search — O(log n)

On a sorted list, compare the target with the middle element and discard half of the remaining range each step. A million items need at most 20 comparisons. The standard bisect module provides bisect_left, bisect_right and insort for searching and inserting into sorted lists.

Jump and Interpolation Search

Jump search jumps ahead in blocks of √n and then scans linearly — O(√n). Interpolation search estimates the position from the values (like opening a dictionary near "P" for "Python") — O(log log n) on uniformly distributed data, but O(n) in the worst case.

Choosing in Practice

For repeated membership tests, a set or dict gives O(1) average lookups and beats every search algorithm. Use binary search when data is already sorted and you need ordering-based queries (e.g. "the first price above 500").

Examples

Linear search

Python

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

marks = [72, 45, 91, 38, 66]
print(linear_search(marks, 91), linear_search(marks, 100))
print(91 in marks, marks.index(91))

Output

2 -1
True 2

Binary search: iterative and recursive, with step counting

Python

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

def binary_search_recursive(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return binary_search_recursive(items, target, mid + 1, high)
    return binary_search_recursive(items, target, low, mid - 1)

data = list(range(0, 2_000_000, 2))          # one million sorted even numbers
print(binary_search(data, 1_234_568))
print(binary_search(data, 7))
print(binary_search_recursive([3, 8, 15, 21, 42], 21))

Output

(617284, 17)
(-1, 20)
3

The bisect module

Python

import bisect

prices = [99, 199, 299, 499, 999, 1999]
print(bisect.bisect_left(prices, 499), bisect.bisect_right(prices, 499))
first_above_500 = prices[bisect.bisect_right(prices, 500)]
print("first price above 500:", first_above_500)
bisect.insort(prices, 650)
print(prices)

def grade(score, cutoffs=(40, 60, 75, 90), grades="FDCBA"):
    return grades[bisect.bisect(cutoffs, score)]
print([grade(s) for s in (33, 59, 60, 88, 95)])

Output

3 4
first price above 500: 999
[99, 199, 299, 499, 650, 999, 1999]
['F', 'D', 'C', 'B', 'A']

Jump search and interpolation search

Python

import math

def jump_search(items, target):
    n = len(items)
    step = int(math.sqrt(n))
    prev = 0
    while prev < n and items[min(prev + step, n) - 1] < target:
        prev += step
    for i in range(prev, min(prev + step, n)):
        if items[i] == target:
            return i
    return -1

def interpolation_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high and items[low] <= target <= items[high]:
        if items[high] == items[low]:
            return low if items[low] == target else -1
        pos = low + (target - items[low]) * (high - low) // (items[high] - items[low])
        if items[pos] == target:
            return pos
        if items[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    return -1

data = list(range(10, 1010, 10))
print(jump_search(data, 730), jump_search(data, 735))
print(interpolation_search(data, 730), interpolation_search(data, 5))

Output

72 -1
72 -1

Common Mistakes

Running binary search on unsorted data.
Computing mid incorrectly or using low < high instead of low <= high, missing the last element.
Sorting data just to do a single search — a linear search is cheaper for one lookup.
Writing custom search loops where a set, dict or bisect is simpler and faster.

Key Points to Remember

Linear search: O(n), works on any data.
Binary search: O(log n), requires sorted data; bisect implements it.
Jump search O(√n); interpolation search O(log log n) on uniform data.
Sets and dicts give O(1) membership for repeated lookups.

Practice the examples

Change an input, predict the result, then compare it with the output. Explain why the result changes.

Try Linear search in Webnest Codelab Try Binary search: iterative and recursive, with step counting in Webnest Codelab Try The bisect module in Webnest Codelab Try Jump search and interpolation search in Webnest Codelab