Python Language Tutorial => Getting the index for sorted sequences:...

Example

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

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

PDF - Download Python Language for free

Previous Next

Python Language

Fastest Entity Framework Extensions

Example

Got any Python Language Question?

Python Language

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

Fastest Entity Framework Extensions

Example

Got any Python Language Question?