使用分治法查找相邻差≤1数组中目标值索引的代码bug排查

你的代码存在3个核心逻辑错误，直接导致部分元素查找失败：

• 递归分支选择逻辑完全不符合数组性质：你当前当abs(x[mid] - k) <=1时仅搜索左半段，否则仅搜索右半段，没有利用相邻元素差绝对值≤1的性质做正确剪枝，且完全遗漏了差值≤1时目标可能在右半段的情况
• 右半段递归的索引偏移逻辑存在边界问题，部分场景会出现索引计算偏差
• 缺失左半段查找失败后的 fallback 逻辑：当差值≤1时，左右半段都可能存在目标，仅搜索单侧必然会漏查

以你给出的测试数组x = [1,2,3,4,5,4,3,3,2,3,4,5,6,7,8]查找元素6为例：

首次调用数组长度为15，mid=7，对应元素为3，abs(3-6)=3>1，代码直接进入右半段递归，传入子数组为[3,2,3,4,5,6,7,8]，偏移量为7
该子数组长度为8，mid=4，对应元素为5，abs(5-6)=1<=1，代码直接进入左半段递归，左半段子数组为[3,2,3,4]，不存在元素6，最终返回-1

查找索引为8的元素2时同理，差值≤1时仅搜索左半段，直接遗漏了右半段的目标元素。

正确的剪枝逻辑应该基于数组特性设计：

1. 若x[mid] - k > 1：mid右侧所有元素最小为x[mid] - (右侧元素个数)，必然大于k，只需搜索左半段
2. 若k - x[mid] > 1：mid左侧所有元素最大为x[mid] + (左侧元素个数)，必然小于k，只需搜索右半段
3. 若abs(x[mid] -k) <=1：左右半段都可能存在目标，先搜索左半段，左半段未找到再搜索右半段

修正后的代码如下：

def find(x, k, z):
    # 边界处理：数组为空直接返回-1
    if len(x) == 0:
        return -1
    # 长度为1时直接判断
    if len(x) == 1:
        return z if x[0] == k else -1
    mid = len(x) // 2
    if x[mid] == k:
        return mid + z
    # 剪枝逻辑
    if x[mid] - k > 1:
        # 只搜左半段
        return find(x[:mid], k, z)
    elif k - x[mid] > 1:
        # 只搜右半段，偏移量为z + mid，因为x[mid:]的0号索引对应原数组的mid+z
        return find(x[mid:], k, z + mid)
    else:
        # 差值≤1，先搜左半段，没找到再搜右半段
        left_res = find(x[:mid], k, z)
        return left_res if left_res != -1 else find(x[mid:], k, z + mid)

用你的测试数组验证修正后的代码：

• 查找元素6返回12，符合实际位置
• 查找元素2可返回1（第一个出现的位置），如果需要返回最后一个出现的位置，调整左右搜索顺序即可

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