Python Bisect - Binary Search

Python Bisect - Binary Search

  1. bisect.bisect_left() Overview
  2. Applications of bisect_left()
  3. bisect.bisect_right() Overview
  4. Applications of bisect_right()
Note

If you want to understand Binary Search in detail, then refer to the binary search algorithm article.

In this article, we will see how to use Python built-in modules to perform Binary Search. The bisect module is based on the bisection method for finding the roots of functions. It consists of 6 functions: bisect(), bisect_left(), bisect_right(), insort(), insort_left(), insort_right() which allows us to find index of an element or insert element in right position in a list. It also helps to keep the list sorted after each insertion. But for them to work properly, we have to make sure that the array is already sorted.

bisect.bisect_left() Overview

It is used to locate the leftmost insertion point of a number x inside a sorted list. If x is already present in the list, then new x will be inserted in the leftmost position among all x in the list.

Syntax

bisect_left(arr, x, lo = 0, hi = len(a))

Parameters

arr The input list
x The element whose insertion point we are locating.
lo It helps to specify the starting index of a subset of a list. The default value is 0.
hi It helps to specify the ending index of a subset of a list. The default value is len(arr).

Return

It returns an insertion point that partitions the array into two halves: the first with all values smaller than x and the second with all values larger than x.

Applications of bisect_left()

Find the first occurrence of an element

from bisect import bisect_left 
 
def binary_search(a, x): 
    i = bisect_left(a, x) 
    if i != len(a) and a[i] == x: 
        return i 
    else: 
        return -1
 
a  = [1, 2, 3, 3, 3] 
x = int(3) 
res = binary_search(a, x) 
if res == -1: 
    print("Element not Found") 
else: 
    print("First occurrence of", x, "is at index", res)

Output:

First occurrence of 3 is at index 2

Findthe greatest value smaller than x

from bisect import bisect_left 
  
def binary_search(a, x): 
    i = bisect_left(a, x) 
    if i: 
        return (i-1) 
    else: 
        return -1
  
# Driver code 
a  = [1, 2, 4, 4, 8] 
x = int(7) 
res = binary_search(a, x) 
if res == -1: 
    print("There is no value smaller than", x) 
else: 
    print("Largest value smaller than", x, " is at index", res) 

Output:

Largest value smaller than 7 is at index 3

bisect.bisect_right() Overview

It is used to return the rightmost insertion point of a number x inside a sorted list. If x is already present in the list, then new x will be inserted in the rightmost position among all x in the list.

Syntax

bisect_right(arr, x, lo = 0, hi = len(a))

Parameters

arr The input list
x The element whose insertion point we are locating.
lo It helps to specify the starting index of a subset of a list. The default value is 0.
hi It helps to specify the ending index of a subset of a list. The default value is len(arr).

Return

It returns an insertion point that partitions the array into two halves: the first with all values <= x and the second with all values > x.

Applications of bisect_right()

Find the last occurrence of an element

from bisect import bisect_right 
  
def binary_search(a, x): 
    i = bisect_right(a, x) 
    if i != len(a)+1 and a[i-1] == x: 
        return (i-1) 
    else: 
        return -1
  
a  = [1, 2, 4, 4] 
x = int(4) 
res = binary_search(a, x) 
if res == -1: 
    print(x, "is absent") 
else: 
    print("Last occurrence of", x, "is present at", res) 

Output:

Last occurrence of 4 is present at 3

Related Article - Python Algorithm

  • Smith-Waterman Algorithm in Python
  • Rabin-Karp Algorithm in Python
  • Union-Find Algorithm in Python
  • Depth-First Search in Python
  • Sieve of Eratosthenes in Python
  • Linear Search in Python