二分查找变体实现：目标不在列表时输出插入位置前后元素

这个需求核心是在有序数组中，找到小于目标值的最大元素和大于目标值的最小元素——也就是目标值插入位置的左右邻居。下面是具体实现思路和代码：

实现思路 #

1. 用二分查找定位到第一个大于目标值的元素索引pos，这个位置就是目标值应该插入的位置
2. 左侧边界元素是pos-1对应的元素（仅当pos>0时存在）
3. 右侧边界元素是pos对应的元素（仅当pos<数组长度时存在）
4. 特殊边界处理：
   • 目标值比所有元素都小：仅返回数组第一个元素
   • 目标值比所有元素都大：仅返回数组最后一个元素

Python代码实现 #

def find_insert_bounds(nums, target):
    left, right = 0, len(nums)
    # 二分查找第一个大于target的元素位置
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > target:
            right = mid
        else:
            left = mid + 1
    # 组装结果
    res = []
    if left > 0:
        res.append(nums[left-1])
    if left < len(nums):
        res.append(nums[left])
    return res

# 测试用例
nums = [1, 2, 4, 7, 7, 8, 9]
print(find_insert_bounds(nums, 5))   # 输出 [4,7]
print(find_insert_bounds(nums, 0))   # 输出 [1]
print(find_insert_bounds(nums, 10))  # 输出 [9]
print(find_insert_bounds(nums, 7))   # 输出 [7,8]

代码说明 #

• 初始right设为len(nums)，是为了兼容目标值大于所有元素的场景，此时left最终会等于数组长度
• 循环条件left < right确保每次迭代都能缩小查找范围，不会出现死循环
• 最终的left就是目标值的插入位置，以此为基准就能快速获取左右边界元素

内容的提问来源于stack exchange，提问作者Jisoo Kim