Implementing the Bisect Module for Sorted Lists

The bisect module in Python provides functions for manipulating sorted lists. These functions are highly efficient, often outperforming manual implementations, and are crucial for tasks involving searching and insertion into ordered data structures. Your challenge is to reimplement two core functions of this module: bisect_left and bisect_right.

Problem Description

You are tasked with creating two Python functions, my_bisect_left and my_bisect_right, that behave identically to bisect.bisect_left and bisect.bisect_right respectively. These functions will operate on sorted lists and efficiently determine insertion points for new elements.

my_bisect_left(a, x, lo=0, hi=None): This function should return an insertion point i such that all elements in a[:i] are less than x, and all elements in a[i:] are greater than or equal to x. In simpler terms, it finds the leftmost position where x can be inserted without violating the sorted order.

my_bisect_right(a, x, lo=0, hi=None): This function should return an insertion point i such that all elements in a[:i] are less than or equal to x, and all elements in a[i:] are greater than x. This finds the rightmost position where x can be inserted without violating the sorted order.

Key Requirements:

• Both functions must accept a sorted list a, a value x to search for/insert, and optional lo (low) and hi (high) indices to define the search range within a.
• If hi is not provided, it should default to len(a).
• If lo is not provided, it should default to 0.
• The functions must maintain the sorted order of the list after insertion. While you are not implementing the insertion itself, the returned index is critical for this.
• The core logic should utilize a binary search algorithm for efficiency.

Expected Behavior:

• For my_bisect_left, if x is already present in a, the returned index will be the index of the first occurrence of x.
• For my_bisect_right, if x is already present in a, the returned index will be the index immediately after the last occurrence of x.
• If x is smaller than all elements in a, the index lo (or 0) should be returned.
• If x is larger than all elements in a, the index hi (or len(a)) should be returned.

Edge Cases to Consider:

• Empty list a.
• x being smaller than all elements.
• x being larger than all elements.
• x being equal to existing elements (duplicates).
• lo and hi defining a sub-range that includes duplicates.

Examples

Example 1:

Input:
a = [1, 2, 4, 4, 5]
x = 4
lo = 0
hi = 5

Output for my_bisect_left: 2
Output for my_bisect_right: 4

Explanation:

• my_bisect_left returns 2 because a[2] is the first 4. Elements before index 2 ([1, 2]) are less than 4. Elements from index 2 onwards ([4, 4, 5]) are greater than or equal to 4.
• my_bisect_right returns 4 because it's the position after the last 4. Elements before index 4 ([1, 2, 4, 4]) are less than or equal to 4. Elements from index 4 onwards ([5]) are greater than 4.

Example 2:

Input:
a = [10, 20, 30, 40, 50]
x = 25
lo = 0
hi = 5

Output for my_bisect_left: 2
Output for my_bisect_right: 2

Explanation:

• my_bisect_left returns 2. Elements before index 2 ([10, 20]) are less than 25. Elements from index 2 onwards ([30, 40, 50]) are greater than or equal to 25.
• my_bisect_right returns 2. Elements before index 2 ([10, 20]) are less than or equal to 25. Elements from index 2 onwards ([30, 40, 50]) are greater than 25.

Example 3: (Edge Case - Sub-range with duplicates)

Input:
a = [1, 2, 2, 2, 3, 4, 5]
x = 2
lo = 1
hi = 5 # Sub-range: [2, 2, 2, 3]

Output for my_bisect_left: 1
Output for my_bisect_right: 4

Explanation:

• The search is confined to indices 1 through 4 (exclusive of 5).
• my_bisect_left within a[1:5] ([2, 2, 2, 3]) finds the leftmost 2 at index 1 relative to the original list.
• my_bisect_right within a[1:5] finds the insertion point after the last 2, which is index 4 relative to the original list.

Constraints

• The input list a will always be sorted in non-decreasing order.
• The list a can contain duplicate elements.
• The elements in a and the value x will be comparable (e.g., all integers, all strings).
• The length of a can be up to 10^5.
• The solution should have a time complexity of O(log n), where n is the length of the list a (or the sub-range defined by lo and hi).

Notes

• You should implement the logic yourself using a binary search approach. Do not simply call bisect.bisect_left or bisect.bisect_right within your functions.
• Consider how to handle the lo and hi parameters to restrict the search space.
• The while loop condition in a binary search is crucial for correctly handling the boundaries and ensuring convergence.
• Think about the loop termination condition and how it relates to the returned index.