# Internalizing Python `bisect_right()`

and `bisect_left()`

** Published:**

Binary search is a popular topic in coding interviews. I was struggling with finding the right template for implementing binary search as it’s annoying to get the equal sign or less than equal sign correctly in the right place. Eventually I decided to use a template similar to `bisect_right()`

and `bisect_left()`

in Python `bisect`

library.

Here I’m going to share how I internalize `bisect_right()`

and `bisect_left()`

so that I no longer need to memorize it.

Of course, if your interviewer gives you a green light to use Python’s built-in libraries, I’d recommend just using it so that you don’t need to reinvent the wheel. And, it also showcases your familiarity with the Python language. Or, you can implement binary search yourself first and then tell your interviewer that there’s actaully Python built-in library that you can use.

# Python’s bisect_right and bisect_left

`bisect_right`

(also known as `bisect`

) and `bisect_left`

perform binary search operations on sorted lists, returning the index where an element needs to be inserted to maintain the sorted order.

`bisect_right`

: Given a sorted list`a`

, find the**right**most insertion position (i.e. index) for value`x`

to maintain sorted order. If`x`

already appears in the list, the insertion point is after (to the right of) any existing entries. In other words, the returned index`i`

partitions the list into two halves such that, all elements less than or equal to`x`

are in`a[:i]`

and all elements greater than`x`

are in`a[i:]`

.`bisect_left`

: Given a sorted list`a`

, find the**left**most insertion position (i.e. index) for value`x`

to maintain sorted order. This function works similarly to`bisect_right`

, but if`x`

already appears in the list, the insertion point returned is the first (or leftmost) occurrence of`x`

. Therefore, the returned index`i`

partitions the list into two halves such that, all elements less than`x`

are in`a[:i]`

and all elements greater than or equal to`x`

are in`a[i:]`

.

Here are the links to their implementations: `bisect_right`

and `bisect_left`

# Internalizing bisect_right and bisect_left

To truly understand these functions, I’ll start by creating simplified versions of them and then gradually refine them to match the Python library implementations.

Let’s start with this code for `bisect_right`

that does the same thing but is easier to understand in my opinion:

```
def bisect_right(a: List[int], target: int) -> int:
# Assuming `a` is a sorted list
left = 0
# It's possible to insert a new element at (last index of a) + 1 if the new element is greater than all existing elements
right = len(a)
while left < right:
middle = (left + right) // 2
if target > a[middle]:
# The insertion position for `target` must be greater than `middle`
left = middle + 1
elif target < a[middle]:
# The insertion position for `target` must be less than or equal to `middle`
right = middle
else:
# If `target == a[middle]`, the right most insertion index must be at least `middle + 1`
# since all elements <= `target` should be to the left of insertion position.
left = middle + 1
return left
```

If we refactor the above code a little bit, we have what’s close to the `bisect_right`

in Python’s `bisect`

library:

```
def bisect_right(a: List[int], target: int) -> int:
left = 0
right = len(a)
while left < right:
middle = (left + right) // 2
if target < a[middle]:
right = middle
else:
left = middle + 1
return left
```

Similarly, we can understand `bisect_left`

by looking at a simpler version:

```
# Assuming `a` is a sorted list
def bisect_left(a: List[int], target: int) -> int:
left, right = 0, len(a)
while left < right:
middle = (left + right) // 2
if target > a[middle]:
# The insertion position for `target` must be greater than `middle`
left = middle + 1
elif target < a[middle]:
# The insertion position for `target` must be less than or equal to `middle`
right = middle
else:
# If `target == a[middle]`, there are two cases to consider:
# 1. If there is only one element whose value equal to target in the list. Then the
# insertion position is equal to `middle`
# 2. If there are more than one element whose value equal to target in the list, then
# we want to keep searching left till we find the first occurrence of `target`. So
# the insertion position must be less than or equal to `middle`.
right = middle
return left
```

And again, if we refactor the above code a little bit, we have what’s close to `bisect_left`

in Python `bisect`

library:

```
def bisect_left(a: List[int], target: int) -> int:
left, right = 0, len(a)
while left < right:
middle = (left + right) // 2
if target > a[middle]:
left = middle + 1
else:
right = middle
return left
```

So now I alway start with writing the simpler version first because it’s easy to just write it out without memorizing it. And then I’ll merge conditions that do the same thing and finally get to the implementation in Python’s `bisect`

library.

# Finding the Leftmost or Rightmost Occurrence of an Element

In many cases, what we want is not the leftmost or rightmost insertion position for a target element in a sorted list. Instead, we want to find the leftmost or rightmost occurrence of that element. We can modify the return value of the above code to achieve this. E.g. if we want to find the rightmost element that is less than or equal to target, we will return `left - 1`

instead in `bisect_right`

. If `left - 1`

< 0, this means all elements in the list are greater than target.

# A note on integer overflow

In other programming languages (e.g. C++) where there’s a limit on the size of integer, you might want to calculate `middle`

by `middle = left + (right - left) // 2`

to avoid integer overflow.

Python doesn’t have a limit on integer value so it’s ok to do `middle = (left + right) // 2`