Implementing the bisect Module in Python

The bisect module in Python provides functions for binary searching and inserting elements into sorted lists while maintaining their sorted order. Implementing this module yourself is a great exercise in understanding binary search algorithms and how they can be applied to maintain sorted data structures efficiently. This challenge asks you to recreate the core functionality of bisect_left and bisect_right from the standard library.

Problem Description

Your task is to implement two functions, bisect_left(list, x) and bisect_right(list, x), which mimic the behavior of the bisect_left and bisect_right functions from Python's bisect module. These functions perform binary searches on a sorted list to find the insertion point for a given element x.

• bisect_left(list, x): Finds the index at which x should be inserted into list to maintain sorted order, such that all elements before the insertion point are strictly less than x. If x is already present in list, the insertion point will be before any existing entries of x.
• bisect_right(list, x): Finds the index at which x should be inserted into list to maintain sorted order, such that all elements before the insertion point are less than or equal to x. If x is already present in list, the insertion point will be after any existing entries of x.

You should implement these functions using a binary search algorithm. The functions should handle empty lists correctly.

Examples

Example 1:

Input: list = [1, 3, 4, 6, 8, 9], x = 5
Output: bisect_left(list, x) -> 3
Output: bisect_right(list, x) -> 3
Explanation: 5 should be inserted at index 3 to maintain sorted order.  Both functions return the same index in this case.

Example 2:

Input: list = [1, 3, 4, 6, 8, 9], x = 0
Output: bisect_left(list, x) -> 0
Output: bisect_right(list, x) -> 0
Explanation: 0 should be inserted at the beginning of the list.

Example 3:

Input: list = [1, 3, 4, 6, 8, 9], x = 10
Output: bisect_left(list, x) -> 6
Output: bisect_right(list, x) -> 6
Explanation: 10 should be inserted at the end of the list.

Example 4:

Input: list = [1, 2, 2, 2, 3, 4], x = 2
Output: bisect_left(list, x) -> 1
Output: bisect_right(list, x) -> 4
Explanation: bisect_left finds the leftmost insertion point, while bisect_right finds the rightmost.

Example 5:

Input: list = [], x = 5
Output: bisect_left(list, x) -> 0
Output: bisect_right(list, x) -> 0
Explanation:  Handles the empty list case correctly.

Constraints

• The input list will contain only comparable elements (e.g., numbers, strings).
• The input list will be sorted in ascending order.
• The input x will be a comparable element.
• The length of the input list will be between 0 and 1000 (inclusive).
• The time complexity of your solution should be O(log n), where n is the length of the list.

Notes

• Implement a binary search algorithm to efficiently find the insertion point.
• Pay close attention to the difference between bisect_left and bisect_right in how they handle existing elements equal to x.
• Consider edge cases such as empty lists and elements smaller or larger than all elements in the list.
• You are not required to implement the entire bisect module, only the bisect_left and bisect_right functions.
• The list is not allowed to be modified. The functions should return the index where the element should be inserted.