The Algorithms - Python Python TheAlgorithms/Python

Search Algorithms in TheAlgorithms/Python

Seven search strategies from a simple scan to partition-based selection, each with a different trade-off.

7 stops ~14 min Verified 2026-05-05

What you will learn

How linear search scans every element and why that is sometimes the right choice
How binary search halves the search space each step and why sorted order is the prerequisite
How jump search trades more comparisons per step for fewer total block boundary tests
How interpolation search uses value distribution to estimate probe position
How exponential search finds a bound before delegating to binary search
How quickselect uses partitioning to find the k-th smallest element without sorting
How ternary search divides the search space into thirds and when that helps

Prerequisites

Comfort reading Python while-loops and index arithmetic
Basic familiarity with sorted collections and what O(log n) means
No prior knowledge of any specific search algorithm required

1 / 7

Linear search: scan every element until found

searches/linear_search.py:30

Iterate through every element in order and return the index of the first match, with no precondition on sort order.

Linear search has a reputation as the naive approach, but it is the only correct choice when the collection is unsorted and sorting it first would cost more than a single scan. The four lines here are as concise as the algorithm can be: enumerate pairs each element with its index, the comparison fires on the first match, and return -1 signals not-found after the loop exhausts without matching. The absence of any precondition check is intentional: linear search imposes no constraint on input order, so there is nothing to validate. The deeper tour covers the recursive variant in the same file, which demonstrates that linear search expressed recursively still has the same O(n) worst-case cost.

Key takeaway

Linear search needs no precondition on sort order; its cost is always O(n) in the worst case, which is acceptable when the list is short or unsorted.

    for index, item in enumerate(sequence):
        if item == target:
            return index
    return -1

2 / 7

Binary search: halve the search space at every step

searches/binary_search.py:200

Maintain left and right bounds, compute the midpoint each iteration, and shrink the bounds based on the comparison result.

Binary search's O(log n) guarantee rests on one precondition: the collection must be sorted. The first two lines enforce that contract with a pairwise check from the standard library. After validation, left and right bound the active search window. Each iteration computes the midpoint as left + (right - left) // 2 rather than (left + right) // 2 to avoid integer overflow in languages where that matters. If the midpoint element matches, return immediately. If the target is smaller, narrow right; if larger, narrow left. When the bounds cross, the target is not present. For a deep look at all nine variants in this file, see the deeper tour.

Key takeaway

Binary search achieves O(log n) by halving the active window each step, but only works correctly on a sorted collection.

    if any(a > b for a, b in pairwise(sorted_collection)):
        raise ValueError("sorted_collection must be sorted in ascending order")
    left = 0
    right = len(sorted_collection) - 1

    while left <= right:
        midpoint = left + (right - left) // 2
        current_item = sorted_collection[midpoint]
        if current_item == item:
            return midpoint
        elif item < current_item:
            right = midpoint - 1
        else:
            left = midpoint + 1
    return -1

3 / 7

Jump search: skip blocks, then scan the last one

searches/jump_search.py:38

Jump forward in blocks of size sqrt(n) until the block boundary exceeds the target, then scan back linearly within that block.

Jump search occupies the space between linear O(n) and binary O(log n): it runs in O(sqrt(n)), which outperforms linear search on large sorted arrays while needing fewer comparisons than pure linear scan. The key design choice is the block size. Setting it to math.sqrt(arr_size) minimises total comparisons by balancing the cost of the jump phase against the cost of the final linear scan. The first while loop jumps forward one block at a time until the block's right boundary is at or above the target. The second while loop then scans left-to-right within that block to find the exact position. See the deeper tour for the full doctest breakdown and complexity proof.

Key takeaway

Jump search runs in O(sqrt(n)) by doing coarse block jumps first and a fine linear scan second, avoiding binary search's overhead on disk-sequential reads.

    arr_size = len(arr)
    block_size = int(math.sqrt(arr_size))

    prev = 0
    step = block_size
    while arr[min(step, arr_size) - 1] < item:
        prev = step
        step += block_size
        if prev >= arr_size:
            return -1

    while arr[prev] < item:
        prev += 1
        if prev == min(step, arr_size):
            return -1
    if arr[prev] == item:
        return prev
    return -1

4 / 7

Interpolation search: probe by estimated position

searches/interpolation_search.py:42

Compute the probe index by linear interpolation between the left and right values, converging faster on uniformly distributed data.

Binary search always probes the midpoint, which is optimal only when the data is uniformly distributed. Interpolation search instead estimates where the target probably sits based on its value relative to the current range boundaries: the formula on lines 52-54 scales the target's position proportionally between left and right. On uniformly distributed integer data this converges in O(log log n) expected time, far better than binary search's O(log n). The guard on lines 47-50 handles the edge case where all remaining elements are equal, avoiding a division-by-zero in the formula. The out-of-range check on lines 57-58 catches cases where the distribution is skewed enough that the formula extrapolates outside the array. The algorithm degrades to O(n) on adversarial distributions.

Key takeaway

Interpolation search is O(log log n) expected on uniformly distributed data by probing proportionally by value, but degrades to O(n) on skewed distributions.

    left = 0
    right = len(sorted_collection) - 1

    while left <= right:
        # avoid divided by 0 during interpolation
        if sorted_collection[left] == sorted_collection[right]:
            if sorted_collection[left] == item:
                return left
            return None

        point = left + ((item - sorted_collection[left]) * (right - left)) // (
            sorted_collection[right] - sorted_collection[left]
        )

        # out of range check
        if point < 0 or point >= len(sorted_collection):
            return None

        current_item = sorted_collection[point]
        if current_item == item:
            return point
        if point < left:
            right = left
            left = point
        elif point > right:
            left = right
            right = point
        elif item < current_item:
            right = point - 1
        else:
            left = point + 1
    return None

5 / 7

Exponential search: find the bound, then binary search within it

searches/exponential_search.py:85

Double a bound until it overshoots the target, then binary-search the subarray between the previous bound and the current one.

Exponential search was designed for unbounded or very large sorted collections where the target is likely near the beginning. The doubling loop on lines 91-93 starts at index 1 and doubles bound until sorted_collection[bound] meets or exceeds the target. This takes O(log i) steps where i is the target's index, independent of total collection size. Once the bound is found, lines 95-97 extract the window between the previous bound and the current one and delegate to binary search. The total cost is O(log i). That is faster than a full binary search when the target is near the start and the collection is large or its length is unknown. The early-return for index 0 on lines 88-89 the doubling loop starts at bound = 1 and never checks sorted_collection[0] directly.

Key takeaway

Exponential search finds the right subarray in O(log i) time, making it fast when the target is near the start of a large or unbounded sorted collection.

    if list(sorted_collection) != sorted(sorted_collection):
        raise ValueError("sorted_collection must be sorted in ascending order")

    if sorted_collection[0] == item:
        return 0

    bound = 1
    while bound < len(sorted_collection) and sorted_collection[bound] < item:
        bound *= 2

    left = bound // 2
    right = min(bound, len(sorted_collection) - 1)
    return binary_search_by_recursion(sorted_collection, item, left, right)

6 / 7

Quickselect: partition to find the k-th element without sorting

searches/quick_select.py:41

Partition the list into smaller, equal, and larger groups around a random pivot, then recurse only into the partition containing rank k.

Quickselect answers "what is the k-th smallest element?" without sorting the entire list. Sorting to answer that question would cost O(n log n); quickselect costs O(n) on average. The mechanism mirrors quicksort's partition step: a random pivot divides the list into smaller, equal, and larger. If index falls within the equal range, the pivot is the answer and the function returns immediately. If not, the function recurses into exactly one of the other two partitions with an adjusted index, discarding the other half entirely. That is the key savings: only one recursive branch fires per level, unlike quicksort which fires both. On uniformly distributed data this converges in O(n) expected time.

Key takeaway

Quickselect finds the k-th smallest element in O(n) expected time by recursing into only one partition per level rather than sorting the whole list.

    # index = len(items) // 2 when trying to find the median
    #   (value of index when items is sorted)

    # invalid input
    if index >= len(items) or index < 0:
        return None

    pivot = items[random.randint(0, len(items) - 1)]
    count = 0
    smaller, equal, larger = _partition(items, pivot)
    count = len(equal)
    m = len(smaller)

    # index is the pivot
    if m <= index < m + count:
        return pivot
    # must be in smaller
    elif m > index:
        return quick_select(smaller, index)
    # must be in larger
    else:
        return quick_select(larger, index - (m + count))

7 / 7

Ternary search: split the range into thirds each iteration

searches/ternary_search.py:87

Split the active range at one-third and two-third positions each iteration, then discard the two-thirds that cannot contain the target.

Ternary search divides the active range into three equal parts each iteration and uses two comparisons to determine which third can contain the target. When the target equals one_third or two_third, the function returns immediately. Otherwise it eliminates two-thirds of the remaining range: if the target is smaller than one_third, shrink right; if larger than two_third, advance left; otherwise the target must be in the middle third. Despite eliminating two-thirds instead of one-half per step, ternary search is slower than binary search in practice because it uses two comparisons per step instead of one. The precision guard at line 90 falls back to linear scan when the window is small enough that the probe arithmetic might overflow or produce unhelpful probes. The algorithm is most useful for unimodal functions where a continuous maximum is being located.

Key takeaway

Ternary search makes two comparisons per step to eliminate two-thirds of the range, but binary search is faster in practice because it does the same work with one comparison.

    left = 0
    right = len(array)
    while left <= right:
        if right - left < precision:
            return lin_search(left, right, array, target)

        one_third = (left + right) // 3 + 1
        two_third = 2 * (left + right) // 3 + 1

        if array[one_third] == target:
            return one_third
        elif array[two_third] == target:
            return two_third

        elif target < array[one_third]:
            right = one_third - 1
        elif array[two_third] < target:
            left = two_third + 1

        else:
            left = one_third + 1
            right = two_third - 1
    return -1

Your codebase next

Create code tours for your project

Intraview lets AI create interactive walkthroughs of any codebase. Install the free VS Code extension and generate your first tour in minutes.

Install Intraview Free