1、二分搜索问题 ⑴、设：a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置I和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。 ⑵、设：有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标I，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。 ⑶、用I，j做参数，且采用传递引用或指针的形式带回值。

1、(⑴) 改写后的二分搜索算法如下：

def binary_search(a, x):
    left = 0
    right = len(a) - 1
    i = -1  # 小于x的最大元素位置
    j = -1  # 大于x的最小元素位置
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            i = mid
            j = mid
            break
        elif a[mid] < x:
            i = mid
            left = mid + 1
        else:
            j = mid
            right = mid - 1
    return i, j

当搜索元素 `x` 不在数组中时，返回小于 `x` 的最大元素位置 `i` 和大于 `x` 的最小元素位置 `j`。当搜索元素在数组中时，`i` 和 `j` 均为 `x` 在数组中的位置。

(⑵) 设计的算法如下：

def find_index(n, t):
    left = 0
    right = n - 1
    while left <= right:
        mid = (left + right) // 2
        if t[mid] == mid:
            return mid
        elif t[mid] < mid:
            left = mid + 1
        else:
            right = mid - 1
    return -1

该算法的时间复杂度为 $O(\log n)$。

(⑶) 改写后的二分搜索算法可以用以下方式返回 `i` 和 `j`：

def binary_search(a, x, i, j):
    left = 0
    right = len(a) - 1
    while left <= right:
        mid = (left + right) // 2
        if a[mid] == x:
            i.value = mid
            j.value = mid
            break
        elif a[mid] < x:
            i.value = mid
            left = mid + 1
        else:
            j.value = mid
            right = mid - 1

在调用该函数时，需要先创建两个变量 `i` 和 `j`，并将它们传递给函数：

from ctypes import c_int

i = c_int(-1)  # 小于x的最大元素位置
j = c_int(-1)  # 大于x的最小元素位置
binary_search(a, x, i, j)
print(i.value, j.value)