# Python Bisect - Binary Search

Harshit Jindal Oct 10, 2023
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:
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
``````

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.