二分搜索递归实现：指定分割因子下递归次数统计及元素访问问题

嘿，我来帮你搞定这两个问题——先理清列表元素的访问方式，再给你实现带递归调用次数统计的两种分割因子的二分搜索～

一、先搞懂如何访问列表haystack的元素 #

在Python里，列表的元素是通过索引来访问的，索引从0开始计数：

• 第一个元素：haystack[0]
• 第n个元素：haystack[n-1]
• 如果你计算出了某个位置（比如中间点mid），直接用haystack[mid]就能拿到对应位置的元素。

举个简单的示例：

haystack = [1, 3, 5, 7, 9]
print(haystack[2])  # 输出5，因为索引2对应列表的第三个元素

二、带递归调用次数统计的二分搜索实现 #

我们可以用一个可变对象（比如列表，因为递归中修改可变对象的内容会被保留）来统计调用次数，避免使用全局变量，代码更优雅。

1. 分割因子为2的情况（标准二分搜索） #

每次递归把搜索空间均分为两半（向下取整），代码如下：

def binary_search_factor2(haystack, target, low, high, count):
    # 每次进入递归函数，计数加1
    count[0] += 1
    # 递归终止条件：搜索空间为空，说明目标不存在
    if low > high:
        return -1
    # 计算中间位置（用low + (high-low)//2避免直接(low+high)//2可能的溢出）
    mid = low + (high - low) // 2
    if haystack[mid] == target:
        return mid
    elif haystack[mid] > target:
        # 目标在左半部分，缩小搜索空间到[low, mid-1]
        return binary_search_factor2(haystack, target, low, mid-1, count)
    else:
        # 目标在右半部分，缩小搜索空间到[mid+1, high]
        return binary_search_factor2(haystack, target, mid+1, high, count)

# 使用示例
if __name__ == "__main__":
    haystack = [1,2,3,4,5,6,7,8,9,10]
    target = 7
    # 用列表存计数：因为列表是可变对象，递归中修改元素会被共享
    count = [0]
    result = binary_search_factor2(haystack, target, 0, len(haystack)-1, count)
    print(f"目标位置：{result}，递归调用次数：{count[0]}")

2. 分割因子为3的情况（三分分割） #

每次递归把搜索空间分成1/3和2/3两部分（向下取整），先搜索1/3的区域，没找到再搜索剩下的2/3区域：

def binary_search_factor3(haystack, target, low, high, count):
    count[0] += 1
    if low > high:
        return -1
    # 计算分割点，将空间分为[low, split-1]（1/3部分）和[split+1, high]（2/3部分）
    split = low + (high - low) // 3
    if haystack[split] == target:
        return split
    elif haystack[split] > target:
        # 目标在左1/3区域
        return binary_search_factor3(haystack, target, low, split-1, count)
    else:
        # 目标在右2/3区域
        return binary_search_factor3(haystack, target, split+1, high, count)

# 使用示例
if __name__ == "__main__":
    haystack = [1,2,3,4,5,6,7,8,9,10,11,12]
    target = 9
    count = [0]
    result = binary_search_factor3(haystack, target, 0, len(haystack)-1, count)
    print(f"目标位置：{result}，递归调用次数：{count[0]}")

补充说明 #

• 为什么用count = [0]而不是普通整数？因为Python中整数是不可变对象，递归里直接修改普通整数不会影响外部的计数；而列表是可变对象，修改它的元素会被所有递归调用共享。
• 一定要确保你的haystack是有序的！二分搜索的核心前提就是有序列表，否则结果会完全错误哦。

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