递归二分查找函数bs返回None问题：旋转数组找最小值

你的递归函数bs返回None主要有两个核心问题，咱们一步步拆解：

1. 递归调用未传递返回值 #

看你的代码，当你调整完L或R后，只是调用了bs(a, tempArray, L, R)，但没有把这个调用的结果return出去。举个例子：当递归深入到某个层级找到了最小值并return a[mid]，这个值只会回到上一层调用，但上一层调用没有把它继续返回，最终回溯到最外层时，没有任何值被返回，自然就得到了None。

2. 边界条件处理缺失 #

你的代码里直接访问tempArray[mid + 1]和tempArray[mid - 1]，但没有考虑mid是数组第一个元素（mid-1=-1）或最后一个元素（mid+1=len(tempArray)）的情况，这会直接引发索引越界错误；另外，当递归收敛到L == R时，也没有对应的终止逻辑，导致无法返回最终的元素。

修复后的代码 #

def bs(a, tempArray, L, R):
    # 递归终止条件：当左右边界重合时，直接返回该位置的元素
    if L == R:
        return a[L]
    mid = (L + R) // 2
    print(mid, L, R)
    # 先做边界检查，避免索引越界
    if mid < R and tempArray[mid + 1] == "T":
        L = mid + 1
    elif mid > 0 and tempArray[mid - 1] == "F":
        R = mid - 1
    elif tempArray[mid] == "F":
        return a[mid]
    # 递归调用时必须return，把结果逐层传递回去
    return bs(a, tempArray, L, R)

a = [3, 4, 5, 6, 7, 1, 2]  # 对应标记：T, T, T, T, T, F,F
end = a[len(a) - 1]
tempArray = []
for i in a:
    tempArray.append("F" if i <= end else "T")
L, R = 0, len(a) - 1
smallest = bs(a, tempArray, L, R)
print(smallest)  # 现在会正确输出1

关键修改点 #

• 新增L == R的终止逻辑，确保递归到最后一个元素时能返回有效值；
• 给mid+1和mid-1的判断加上边界检查（mid < R/mid > 0），避免索引越界；
• 在递归调用前添加return，让找到的最小值能逐层传递回最初的函数调用。

本质上你的思路是把旋转数组转换成T/F标记数组，寻找第一个"F"的位置，这是二分查找的典型变种，修复后就能正常工作啦。

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