CKTIS / Python
Performance and complexity
Count the work that grows with input size and distinguish it from machine-dependent elapsed time.
Version: Python 3.14; repository image, production runtime not attested
Syntax
bisect_left(sorted_values, target)Count the work that grows with input size and distinguish it from machine-dependent elapsed time.
Scanning a sorted list sequentially may inspect every element, while binary search repeatedly halves the interval and uses logarithmically many comparisons. The insertion index alone does not prove membership, so check the bound and value.
Preparing the sorted input and inserting into a list incur separate costs.
Examples
from bisect import bisect_left
values = list(range(0, 32, 2))
def lookup(target):
reads = 0
def key(x):
nonlocal reads
reads += 1
return x
index = bisect_left(values, target, key=key)
found = index < len(values) and values[index] == target
return found, reads
print(lookup(30), lookup(31))
def scan(target):
checks = 0
for item in values:
checks += 1
if item == target:
return True, checks
return False, checks
print(scan(30), scan(31))
Result
(True, 4) (False, 4) (True, 16) (False, 16)
Preparing the sorted input and inserting into a list incur separate costs.