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
| Operation | Average | Worst case |
|---|---|---|
| Linear search | O(n) | O(n) |
| Binary search (sorted data) | O(log n) | O(log n) |
x in set or dictionary lookup | O(1) | O(n) |
Examples
Linear search
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))
2 -1
True 2
Binary search: iterative and recursive, with step counting
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))
(617284, 17)
(-1, 20)
3
The bisect module
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)])
3 4
first price above 500: 999
[99, 199, 299, 499, 650, 999, 1999]
['F', 'D', 'C', 'B', 'A']
Jump search and interpolation search
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))
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)
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, withmid = (low + high) // 2. - If the middle item is smaller than the target, set
low = mid + 1; if larger, sethigh = mid - 1.
Show 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.
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