Expert Python Programming - Third Edition

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