Binary search is a commonly-used search method on sorted arrays/lists. If we need to find element x inside sorted array a, then binary\_search\(a, x\) can be implemented with Python bisect library.

The bisect module

The bisect module is called bisect because it uses a basic bisection algorithm: Given element x and sorted array a, the bisect methods returns an index that splits array a into two parts: one part no larger than x, the other part no smaller than x. There are three bisect methods in the bisect library:

• bisect\_right (alias bisect): returns the location to insert x while keeping a sorted. If x is already in a, then return the location next to the last appearance of x.
• bisect\_left: returns the location to insert x while keeping a sorted. If x is already in a, then return the location of the first appearance of x.

bisect module also has three other methods that inserts x into a while keeping a sorted

• insort\_right (alias insort): inserts x into a at location insect\_right
• insort\_left: inserts x into a at location insect\_left

Some interesting observations of bisect methods

• bisect methods return insertion points: the index of x in a after insertion
• bisect.bisect is a short-hand for bisect\_right and is always the same as bisect\_right.
• When a is sorted, and x is not found in a, bisect is also the same as bisect\_left

What if a is not sorted or a is not in increasing order?

Looking at the source code of bisect, bisect implementation doesn't check if a is properly sorted. Therefore, the behavior of bisect, bisect\_left, and bisect\_right is not defined.