（1）设al0:n-1］是一个已排好序的数组。请改写二分搜索算法，使得当搜索元 素×不在数组中时，返回小于×的最大元素的位置i和大于×的最小元素位置j。 当搜索元素在数组中时，i和j相同，均为×在数组中的位置。

这是一个修改过的二分查找算法，通常称为“扩展二分查找”或“区间搜索”。在这个版本中，我们不仅要找到目标值，还要同时确定其左侧第一个大于目标值的元素和右侧第一个小于目标值的元素的位置。

def extended_binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    i = j = -1  # 初始化最大元素位置i和最小元素位置j为-1

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

        if arr[mid] == target:  # 找到目标元素
            i = j = mid  # 设置相同位置
            break
        elif arr[mid] < target:  # 如果中间元素小于目标，更新左侧边界
            left = mid + 1
            i = mid  # 更新最大元素位置
        else:  # 如果中间元素大于目标，更新右侧边界并保留最小元素位置
            right = mid - 1
            j = mid  # 更新最小元素位置

    return i, j

# 示例：
arr = [1, 3, 5, 6, 8, 9]
target = 7
result = extended_binary_search(arr, target)
print(f"大于{target}的最小元素在索引{i}，小于{target}的最大元素在索引{j}")