用python实现，题目三：二分搜索算法 设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。并对自己的程序进行复杂性分析。

在Python中，你可以通过以下步骤实现这个改进版的二分搜索算法：

def binary_search_with_bounds(a, n, x):
    left = 0
    right = n - 1
    i = j = -1  # 初始化结果位置为-1，表示未找到

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

        if a[mid] == x:
            i = j = mid  # 如果找到了元素，更新位置并退出循环
            break
        elif a[mid] < x:
            left = mid + 1
            if mid > 0 and a[mid - 1] >= x:  # 检查左侧是否满足条件
                i = mid - 1  # 更新小于x的最大位置
        else:
            right = mid - 1
            if mid < n - 1 and a[mid + 1] <= x:  # 检查右侧是否满足条件
                j = mid + 1  # 更新大于x的最小位置

    return i, j

# 示例
a = [1, 3, 4, 6, 8, 9]
n = len(a)
x = 5
result = binary_search_with_bounds(a, n, x)
print(f"当x={x}不在数组中时，小于x的最大元素位置{i}, 大于x的最小元素位置{j}")

复杂性分析：
这个改进的二分搜索算法的时间复杂度仍然是O(log n)，因为它仍然每次将搜索范围减半。空间复杂度是O(1)，因为我们只使用了几个额外的变量，并没有增加对额外数据结构的依赖。如果数组x不在数组a中，它最多需要查找log n次才能确定边界，即最坏的情况下会执行n次比较（包括边界检查）。