Array Bisection in Python

Bisect algorithm maintains a list in sorted order without having to call sort each time an item is added to the list. bisect module in Python defines a number of functions to keep the array in a sorted fashion. The module uses bisection algorithm to do its work. It inserts the element at the correct position without having to sort the array again every time.

Important API

Functions provided in bisect module are

• bisect_left(aList, val, lo=0, hi=len(aList)) : Used to find leftmost insertion point for val in aList to maintain sorted order. lo and hi are optional parameters, used to specify a subset of the list which should be considered. If val is already present in aList, the insertion point will be to the left of any existing entries.
• bisect_right(aList, val, lo=0, hi=len(aList)) : Used to find rightmost insertion point for val in aList to maintain sorted order. lo and hi are optional parameters, used to specify a subset of the list which should be considered. If val is already present in aList, the insertion point will be to the right of any existing entries.
• bisect(aList, val, lo=0, hi=len(aList)) : It is similar to bisect_left(), but returns an insertion point which comes to the right of any existing entries of val in aList.
• insort_left(aList, val, lo=0, hi=len(aList)) : Insert val in aList in sorted order. It is equivalent to invoking the bisect_left() function followed by the aList.insert() method.
• insort_right(aList, val, lo=0, hi=len(aList)) : Insert val in aList in sorted order. It is equivalent to invoking the bisect_right() function followed by the aList.insert() method.
• insort(aList, val, lo=0, hi=len(aList)) : Similar to insort_left(), but val is inserted in aList after any existing entries of val.

Example

Below example shows the use if various functions available in bisect module.

# Program showing application of bisection functions to maintain a list in sorted order
import bisect

# Indexs  0  1   2   3   4   5   6   7  8   9   10  11  12
values = [5, 7, 13, 20, 25, 25, 25, 31, 31, 31, 36, 43, 47]

# 1. Use of bisect, bisect_left and bisect_right routines
print(bisect.bisect(values, 25))
print(bisect.bisect_left(values, 25))
print(bisect.bisect_right(values, 31))

# Output
# 7
# 4
# 10

# 2. Use of insort_right
bisect.insort_right(values, 33)
print(values)

# Output, inserted after rightmost 31
# [5, 7, 13, 20, 25, 25, 25, 31, 31, 31, 33, 36, 43, 47]


# 2. Use of insort_left
bisect.insort_left(values, 23)
print(values)

# Output, inserted after rightmost 20
# [5, 7, 13, 20, 23, 25, 25, 25, 31, 31, 31, 33, 36, 43, 47]

If you start from an empty list and repeatedly use insort to insert the objects into a list, the final list will be sorted.

import bisect

l = [3, 7, 5, 6, 4, 9, 8]

result = []
for e in l:
  bisect.insort(result, e)

print(result)

# Output
# [3, 4, 5, 6, 7, 8, 9]