Horje

GETTING the index for sorted sequences bisect bisect left - Searching - Python
Learn
Python - Searching - Getting the index for sorted sequences bisect bisect left
Getting the index for sorted sequences: bisect.bisect_left()

Sorted sequences allow the use of faster searching algorithms: bisect.bisect_left()1 (opens new window):

import bisect

def index_sorted(sorted_seq, value):
    """Locate the leftmost value exactly equal to x or raise a ValueError"""
    i = bisect.bisect_left(sorted_seq, value)
    if i != len(sorted_seq) and sorted_seq[i] == value:
        return i
    raise ValueError

alist = [i for i in range(1, 100000, 3)] # Sorted list from 1 to 100000 with step 3
index_sorted(alist, 97285) # 32428
index_sorted(alist, 4)     # 1
index_sorted(alist, 97286)

ValueError

For very large sorted sequences the speed gain can be quite high. In case for the first search approximatly 500 times as fast:

%timeit index_sorted(alist, 97285)
# 100000 loops, best of 3: 3 µs per loop
%timeit alist.index(97285)
# 1000 loops, best of 3: 1.58 ms per loop

While it's a bit slower if the element is one of the very first:

%timeit index_sorted(alist, 4)
# 100000 loops, best of 3: 2.98 µs per loop
%timeit alist.index(4)
# 1000000 loops, best of 3: 580 ns per loop


Read Article
https://develop.horje.com/learn/1434/reference

 

Horje