Searching

Searching finds whether a value exists in a collection and, if so, where. Python provides both built-in conveniences and the ability to write searches explicitly.

Linear Search

A linear search examines each element one by one until it finds the target or exhausts the list. It works on any list, sorted or not.

Using the ``in`` operator (membership only) and ``list.index()`` (returns the position). Try it live and search for values of your own:

Try it live ▶

>>> data = [12, 8, -5, 22, 9, 2]
>>> print(7 in data)
False
>>> print(9 in data)
True
>>> print(data.index(9))
4

Go BackOpen In Tab

index() raises ValueError if the value is not in the list. To avoid the exception, check with in first. Try it live:

Try it live ▶

>>> data = [12, 8, -5, 22, 9, 2]
>>> target = 22
>>> if target in data:
...     print(f"Found at index {data.index(target)}")
... else:
...     print("Not found")
...
Found at index 3

Go BackOpen In Tab

Writing Linear Search Explicitly

Writing the search as a loop is useful when you need more control — for example, to return the index on the first match, or to search through a list of objects by a field:

Try it live and search for different targets:

Try it live ▶

>>> def linear_search(data: list, target) -> int:
...     for i, value in enumerate(data):
...         if value == target:
...             return i
...     return -1    # not found
...
>>> data = [12, 8, -5, 22, 9, 2]
>>> print(linear_search(data, 9))
4
>>> print(linear_search(data, 99))
-1

Go BackOpen In Tab

Continuing a Search

To find all occurrences, collect every matching index:

Try it live and find every matching index:

Try it live ▶

>>> def find_all(data: list, target) -> list[int]:
...     return [i for i, v in enumerate(data) if v == target]
...
>>> print(find_all([1, 3, 1, 4, 1], 1))
[0, 2, 4]

Go BackOpen In Tab

Binary Search

Linear search examines up to N elements — slow for large sorted lists. Binary search repeatedly halves the search space, requiring only O(log N) comparisons — but the list must be sorted.

Python’s bisect module provides binary search. Try it live and search the sorted list for other values:

Try it live ▶

>>> import bisect
>>> data = [-5, 2, 8, 9, 12, 22]   # must be sorted
>>> i = bisect.bisect_left(data, 9)
>>> if i < len(data) and data[i] == 9:
...     print(f"Found at index {i}")
... else:
...     print("Not found")
...
Found at index 3

Go BackOpen In Tab

bisect_left(data, target) returns the leftmost position where target could be inserted to keep data sorted. If data[i] == target, the value is present.

Performance Comparison

Search type	Time	Requirement
in / linear	O(N)	Any list
bisect	O(log N)	List must be sorted

For small lists the difference is negligible. For large sorted lists, binary search is dramatically faster.