Course topics

By WebNest Studio Engineering Team

Python Tutorial

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).

Why it matters

Finding an item in a collection is one of the most frequent operations in software, and the method chosen decides whether it takes twenty steps or a million. Binary search is the standard example of an algorithm that is fast because it discards half of the remaining data at each step, and it is asked for in a large share of coding interviews.

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").

Time complexity

OperationAverageWorst case
Linear searchO(n)O(n)
Binary search (sorted data)O(log n)O(log n)
x in set or dictionary lookupO(1)O(n)

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.

Exercise

Implement binary search on a sorted list, returning the index of the target or -1 when it is not present. Then use the bisect module to print the position at which 25 would be inserted into a sorted list.

Expected output: 4, -1, 2 (one per line)

Python · starter code
from bisect import bisect_left


def binary_search(items, target):
    low = 0
    high = len(items) - 1

    # TODO: while the range is not empty, compare the middle item with the target
    #       and continue in the left or the right half

    return -1


numbers = [2, 5, 8, 12, 16, 23, 38]
print(binary_search(numbers, 16))
print(binary_search(numbers, 7))

# TODO: print where 25 would be inserted in [10, 20, 30, 40]
Show hints
  • The loop runs while low <= high, with mid = (low + high) // 2.
  • If the middle item is smaller than the target, set low = mid + 1; if larger, set high = mid - 1.
Show solution
Python · solution
from bisect import bisect_left


def binary_search(items, target):
    low = 0
    high = 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


numbers = [2, 5, 8, 12, 16, 23, 38]
print(binary_search(numbers, 16))
print(binary_search(numbers, 7))

print(bisect_left([10, 20, 30, 40], 25))

Quick quiz

1. What must be true of a list before binary search can be used on it?

  • A. It must be sorted
  • B. It must have an even length
  • C. It must contain no duplicates
  • D. It must contain numbers
Show answer

A. Discarding half of the range is only valid when the items are in order.

2. About how many comparisons does binary search need, at most, for a million sorted items?

  • A. 1,000
  • B. 20
  • C. 500,000
  • D. 1,000,000
Show answer

B. Each step halves the range, and 2 to the power 20 is just over a million.

3. Which standard library module provides binary search on a sorted list?

  • A. search
  • B. heapq
  • C. bisect
  • D. itertools
Show answer

C. bisect_left and bisect_right return the insertion point for a value.

Interview questions

Compare linear search and binary search.

Show answer

Linear search checks each item in turn; it works on any data and takes O(n) time. Binary search repeatedly compares the middle item of the remaining range and discards the half that cannot contain the target; it takes O(log n) time but requires sorted data. If the data is searched once, sorting it first costs more than a linear scan, so binary search pays off when the data is already sorted or is searched many times.

In Python, when would you not write either search by hand?

Show answer

Nearly always. For membership tests and lookups by key, a set or dict gives O(1) average time. For a sorted list, the bisect module provides a tested binary search. For a single search of an unsorted list, in and list.index() do the linear scan in C. Writing the algorithm by hand is mostly an exercise and an interview task.

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 in the playground

Write and run your own code for this topic, or start from the exercise or an example. Runs Python in your browser. Your code for each topic is kept in this browser.

Run the examples

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

WebNest Studio

Written by

WebNest Studio Engineering Team

Practical lessons from developers working with Java, Python, React, databases and production systems.

Led by Vansh Duggal, Founder, WebNest Studio · Full-stack & software engineering