Binary search

Why it costs this much

Each comparison halves the remaining range, so after k steps n / 2^k items remain. That reaches 1 when k equals log₂ n.

Code

import bisect
i = bisect.bisect_left(sorted_items, target)    # O(log n)
found = i < len(sorted_items) and sorted_items[i] == target
# Each step halves the range: n -> n/2 -> n/4 -> ... -> 1 takes log2(n) steps.

Python is the baseline example used across the site.

Common pitfalls

Off-by-one mistakes in lo, hi, and mid are the usual bug. The input must already be sorted, and sorting first costs O(n log n).

Operation by operation

Binary search. Input is sorted and supports O(1) random access. Sorting first costs O(n log n). On a linked list the middle element costs O(n) to reach, so there is no speedup.