Searching in a list

Due to the implementation details of the list type in Python, searching for a specific value in a list isn't a cheap operation. The complexity of the list.index() method is O(n), where n is the number of list elements. Such linear complexity won't be an issue if you don't need to perform many element index lookups, but it can have a negative performance impact in some critical code sections—especially if it is done over very large lists.

If you need to search over a list quickly and often, you can try the bisect module from Python's standard library. The functions in this module are mainly designed for inserting or finding insertion indexes for given values in a way that will preserve the order of the already sorted sequence. This module is used to efficiently find an element index using a bisection algorithm. The following recipe, from the official documentation of the function, finds an element index using binary search:

def index(a, x): 
    'Locate the leftmost value exactly equal to x' 
    i = bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    raise ValueError

Note that every function from the bisect module requires a sorted sequence in order to work. If your list is not in the correct order, then sorting it is a task with at least O(n log n) complexity. This is a worse class than O(n), so sorting the whole list to then perform a single search will not pay off. However, if you need to perform a number of index searches across a large list that rarely changes, using a single sort operation for bisect may prove to be the best trade-off.

If you already have a sorted list, you can also insert new items into that list using bisect without needing to re-sort it.

In the next section, we will see how to use a set instead of a list.