如何用分治法判断降序列表中存在值等于对应索引的元素

这个问题完全可以通过分治算法实现，而且利用数组「元素互不相同、严格降序」的性质，分治实现的时间复杂度可以达到O(logn)，比线性遍历的O(n)效率更高。

核心思路：解决拆分后索引错位问题 #

你之前遇到的拆分后索引不对应的问题，本质是陷入了「必须物理切分原列表」的误区：分治不需要真的把列表拆成多个独立子列表，只需要在递归时传入当前搜索区间在原列表中的左右边界下标，所有比较都基于原列表的真实索引完成，自然不会出现索引错位。

基于数组的性质，我们可以直接推导出区间排除规则，不需要遍历所有元素：
因为数组严格降序、元素互异，对任意索引i < j，一定满足L[i] > L[j]。取当前搜索区间的中间位置mid = (left + right) // 2，可以得到三种情况：

• 若L[mid] == mid：直接命中条件，返回True
• 若L[mid] > mid：mid左侧所有位置的索引都小于mid，且左侧元素都比L[mid]更大，也就是左侧元素值永远大于mid，必然大于左侧的索引值（最大为mid-1），左侧不可能存在匹配，只需要递归搜索右半区间[mid+1, right]
• 若L[mid] < mid：mid右侧所有位置的索引都大于mid，且右侧元素都比L[mid]更小，也就是右侧元素值永远小于mid，必然小于右侧的索引值（最小为mid+1），右侧不可能存在匹配，只需要递归搜索左半区间[left, mid-1]

基准条件补充 #

除了你已经想到的两个基准条件，还需要补充两个边界判断减少不必要的递归：

• 若当前搜索区间左边界大于右边界（left > right），说明区间已经遍历完没有找到匹配，返回False
• 若当前搜索区间右边界对应的元素值L[right] > right：因为数组降序，区间内所有元素都比L[right]大，而区间内最大索引就是right，所有元素值都大于最大索引，不可能存在匹配，直接返回False
• 若当前搜索区间左边界对应的元素值L[left] < 0：因为数组降序，区间内所有后续元素都比L[left]小，也就是全为负数，而索引都是非负整数，不可能存在匹配，直接返回False（即你已经想到的判断）
• 空列表直接返回False

代码实现（Python） #

def check_fixed_point(L):
    # 空列表直接返回False
    if not L:
        return False
    
    def dfs(left, right):
        # 区间越界，无匹配
        if left > right:
            return False
        # 区间左端点值为负，后续全负无匹配
        if L[left] < 0:
            return False
        # 区间右端点值大于右索引，前面全更大无匹配
        if L[right] > right:
            return False
        
        mid = (left + right) // 2
        if L[mid] == mid:
            return True
        elif L[mid] > mid:
            # 排除左半区间，搜右侧
            return dfs(mid + 1, right)
        else:
            # 排除右半区间，搜左侧
            return dfs(left, mid - 1)
    
    # 初始搜索范围是整个列表
    return dfs(0, len(L) - 1)

示例验证 #

拿你给出的例子L = [4,3,2,0]测试：

1. 初始区间left=0，right=3，mid=1，L[1]=3 > 1，排除左半，搜索区间变为[2,3]
2. 新区间mid=2，L[2]=2 == 2，直接返回True，符合预期。

如果你一定要用物理切片的方式拆分列表也可以实现，只需要额外记录当前子列表的起始索引偏移量：子列表中第i个元素对应的原列表索引是offset + i，比较时判断sub_L[i] == offset + i即可，但这种方式会额外占用切片的内存空间，不如直接传边界的方式高效。

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