Looking for python Answers? Try Ask4KnowledgeBase
Looking for python Keywords? Try Ask4Keywords

Python Language Getting the index for sorted sequences: bisect.bisect_left()


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

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)


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