Searching

Contents

Searching#

Linear search is one line: x in xs or a generator expression. Use a set or dict when membership tests will repeat (O(1) average vs O(n)).

if target in xs:                       # O(n) for list, O(1) for set
    ...

first_match = next((x for x in xs if pred(x)), None)

Binary search via bisect for sorted sequences.

from bisect import bisect_left, bisect_right, insort

def index(xs, target):
    """Return index of `target` in sorted `xs`, or -1."""
    i = bisect_left(xs, target)
    if i < len(xs) and xs[i] == target:
        return i
    return -1

insort(xs, new_value)                  # maintains sorted order, O(n) insert

References#

Contents