改进二分搜索：查找目标值或其最近邻元素

传统的二分搜索算法只能判断目标值是否存在于已排序数组中。本文将介绍一种改进的二分搜索算法，即使目标值不存在，也能返回小于目标值的最大元素位置 i 和大于目标值的最小元素位置 j。

算法思路

初始化: 设置搜索范围的边界，i = 0，j = n - 1，其中 n 为数组长度。2. 循环搜索: - 计算中间索引 mid = (i + j) / 2。 - 如果 a[mid] == x，则目标值存在于数组中，返回 mid。 - 如果 a[mid] < x，说明目标值可能在数组的右半部分，更新 i = mid + 1。 - 如果 a[mid] > x，说明目标值可能在数组的左半部分，更新 j = mid - 1。3. 返回结果: 循环结束后，如果未找到目标值，则 i 和 j 分别代表小于目标值的最大元素位置和大于目标值的最小元素位置。如果目标值存在，则 i 和 j 相等，都指向目标值的位置。

伪代码

function binarySearch(a, n, x): i = 0 j = n - 1 while i <= j: mid = (i + j) / 2 if a[mid] == x: return mid if a[mid] < x: i = mid + 1 else: j = mid - 1 return i, j

总结

通过简单的修改，我们扩展了传统二分搜索的功能，使其不仅可以查找目标值，还能提供关于目标值在数组中位置的更多信息。这种改进的算法在实际应用中非常有用，例如在数据库索引、插入排序等场景中都有广泛应用。