Binary Search in Python Using the `bisect` Module

Binary search is an efficient algorithm for finding a specific value in a sorted list or determining the position where that value should be inserted, with a time complexity of O(log N). In contrast, the index method uses linear search with a time complexity of O(N).

1. Custom Binary Search Function :

def bisect(arr, target, start_index=0, end_index=None):
    if start_index < 0:
        raise ValueError('start_index must be non-negative')
    if end_index is None:
        end_index = len(arr)  # Default to the length of the list if end_index is not provided

    while start_index < end_index:
        mid_index = (start_index + end_index) // 2
        if arr[mid_index] < target:
            start_index = mid_index + 1
        else:
            end_index = mid_index

    return start_index

sorted_list = [1, 2, 3, 7, 9, 11, 33]
print(bisect(sorted_list, 23))  # Output: 6

• arr: The sorted list.
• target: The value to search for.
• start_index and end_index: Indices representing the search range (start_index defaults to 0 and end_index defaults to the length of the list).

Logic:

• The function calculates the midpoint mid_index and compares the value at arr[mid_index] with target.
• If target is greater than arr[mid_index], start_index is updated to mid_index + 1 to search the right half.
• If target is less than or equal to arr[mid_index], end_index is updated to mid_index to search the left half.
• The loop continues until start_index is no longer less than end_index, and the function returns start_index, indicating where target should be inserted.

Example:

• Searching for 23 in mylist returns 6, the position where 23 would be inserted.

2. Using the bisect Module:

import bisect

mylist = [1, 2, 3, 7, 9, 11, 33]
print(bisect.bisect(mylist, 23))  # Output: 6

The bisect module from Python's standard library simplifies binary search operations.

• bisect.bisect() (which is equivalent to bisect.bisect_right()) returns the position where target should be inserted to maintain the sorted order of the list. If target is already present, it returns the position after the existing entry.
• Note: For inserting the value at the leftmost position where it could fit, bisect.bisect_left() can be used.

The custom implementation and the bisect module produce the same result, but the bisect module is simpler and easier to maintain.