计算题 请改写二分搜索算法的函数，使得当搜索元素x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。设a[0:n-1]是已排好序的数组。当搜索元素在数组中时，i和j相同，均为x在数组中

二分搜索通常用于在一个有序数组中查找特定元素。为了满足题目要求，我们需要对标准二分搜索稍作修改。首先，我们找到元素x应该插入的位置，如果它不在数组中，我们将得到两个范围：一个是在x左侧的所有元素（最大比x小的元素），另一个是在x右侧的所有元素（最小比x大的元素）。以下是修改后的伪代码：

def modified_binary_search(a, x):
    left = 0
    right = len(a) - 1
    i = j = -1

    while left <= right:
        mid = (left + right) // 2

        # 如果x等于中间元素，直接返回相同的索引位置作为i和j
        if a[mid] == x:
            return mid, mid

        # 如果x小于中间元素，更新右边界并找到比x大但尽可能靠左的元素
        elif a[mid] > x:
            right = mid - 1
            if right >= 0:
                i = mid
        # 否则，x大于中间元素，更新左边界并找到比x小但尽可能靠右的元素
        else:
            left = mid + 1
            if left < len(a):
                j = mid

    # 当搜索结束，x不在数组内，返回i和j
    return i, j

# 示例
a = [1, 3, 5, 6, 8, 9]
x = 4
result = modified_binary_search(a, x)
print(f"小于x的最大元素位置 {result[0]} 和大于x的最小元素位置 {result[1]}")