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

在Python中，我们可以使用递归的方式实现带条件的二分查找。以下是二分搜索算法的实现：

def binary_search_with_conditions(a, n, x):
    left = 0
    right = n - 1
    i = j = -1  # 初始化结果变量

    while left <= right:
        mid = (left + right) // 2
        
        if a[mid] == x:
            i = j = mid  # 如果找到元素，则i和j相等
            break
        elif a[mid] < x:
            left = mid + 1
            i = mid  # 更新小于x的最大元素位置
        else:
            right = mid - 1
            j = mid  # 更新大于x的最小元素位置
            
    return i, j

# 示例：
a = [1, 3, 5, 6, 8, 9]
n = len(a)
x = 7
result = binary_search_with_conditions(a, n, x)
print(f"小于{x}的最大元素位置{i}，大于{x}的最小元素位置{j}")

对于这个算法的时间复杂度分析：
- 在最好的情况下，即目标值恰好位于数组中间，我们只需一次比较就能找到，时间复杂度是O(1)。
- 在最坏的情况下，目标值不在数组内，需要对数组的一半进行比较，每次迭代都会减半搜索范围，因此时间复杂度是O(log n)，这是二分查找的基本特性。
- 平均来说，也是线性对数时间复杂度O(log n)。