Bisect Left in Python

Python’s bisect_left function is implemented as a binary search algorithm. You could certainly implement your own version of bisect_left to understand how it works under the hood. Here’s a simple Python implementation:

1
2
3
4
5
6
7
8
9

def bisect_left(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:  # Move to the right half if target is greater than the mid element
            left = mid + 1
        else:  # Move to the left half if target is less or equal to the mid element
            right = mid
    return left

In this function:

  • arr is a sorted list.
  • target is the element you’re searching for.
  • The function returns the index where the target should be inserted to keep the list sorted.

You can test this function like so:

1

print(bisect_left([1, 2, 4, 5], 3))  # Output: 2

The output is 2 because if you insert 3 at index 2 in the list [1, 2, 4, 5], the list remains sorted.

Difference

The bisect_left function and the classic binary search algorithm are very similar, as they both rely on the concept of binary search to perform operations in a sorted list. However, there’s a fundamental difference in their purpose and behavior.

Classic Binary Search:

  • Classic binary search is used to find if a particular value exists in a sorted list. If the value exists, the algorithm will return the index of that value. If the value does not exist, it typically returns a value to indicate that the search value was not found in the list.

bisect_left function:

  • The bisect_left function in Python is used to find the insertion point for a value in a sorted list to maintain the sorted order of the list. It doesn’t check whether the value exists in the list. Instead, it returns the position where the value should be inserted. If the value is already present in the list, bisect_left will return the position of the first occurrence of that value.

So, in summary, the primary difference is in the intent and the behavior of these two operations: the classic binary search is for finding a value, whereas bisect_left is for finding the correct insertion point for a value in a sorted list.