递归实现二分查找与插入排序遇缩进错误，求问题排查方案

一、先解决递归二分查找的问题 #

你的二分查找代码里有个明显的语法错误，Python里没有else if:这种写法，正确的是elif，而且这里你根本不需要额外的分支判断，直接在else块里对比元素和中间值的大小即可。另外代码整体缩进没问题，但那个错误语法会直接导致编译失败。

修正后的递归二分查找代码：

def binarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist) // 2
        if alist[midpoint] == item:
            return True
        # 去掉错误的else if:，直接判断元素和中间值的大小关系
        if item < alist[midpoint]:
            return binarySearch(alist[:midpoint], item)
        else:
            return binarySearch(alist[midpoint+1:], item)

testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))  # 输出False
print(binarySearch(testlist, 13)) # 输出True

二、递归插入排序的问题更集中：缩进混乱+逻辑缺失 #

你的插入排序代码有几个核心问题：

1. 函数定义没接收i参数，但内部直接用了i，得给i加默认值i=1（插入排序从第二个元素开始处理）
2. 函数外的while循环完全没缩进，属于全局代码，而且position和currentvalue都没定义，会直接报错
3. 递归逻辑混杂，把两种插入逻辑揉在了一起，导致代码完全无法正常运行

我整理了两种符合递归思维的插入排序写法，保证排序后输出和你二分查找的测试列表一致：

写法一：从后往前递归（更贴合递归拆分问题的思路）

def insertionSort(arr):
    # 递归终止条件：列表长度<=1时无需排序
    if len(arr) <= 1:
        return arr
    # 先递归排序前n-1个元素
    sorted_part = insertionSort(arr[:-1])
    # 取出最后一个元素，插入到已排序部分的正确位置
    last_element = arr[-1]
    i = len(sorted_part) - 1
    # 找到合适的插入位置
    while i >= 0 and sorted_part[i] > last_element:
        i -= 1
    # 插入元素并返回
    sorted_part.insert(i + 1, last_element)
    return sorted_part

# 用无序列表测试，排序后和你的二分查找测试列表完全一致
unsorted_list = [13, 0, 42, 2, 19, 8, 1, 17, 32]
sorted_list = insertionSort(unsorted_list)
print(sorted_list)  # 输出[0, 1, 2, 8, 13, 17, 19, 32, 42]

写法二：从左到右逐个插入（贴近你原本的思路）

def insertionSort(arr, i=1):
    # 递归终止条件：i超出列表长度时返回已排序的列表
    if i >= len(arr):
        return arr
    current_value = arr[i]
    position = i
    # 把当前元素插入到前面已排序的正确位置
    while position > 0 and arr[position - 1] > current_value:
        arr[position] = arr[position - 1]
        position -= 1
    arr[position] = current_value
    # 递归处理下一个元素
    return insertionSort(arr, i + 1)

unsorted_list = [13, 0, 42, 2, 19, 8, 1, 17, 32]
insertionSort(unsorted_list)
print(unsorted_list)  # 输出[0, 1, 2, 8, 13, 17, 19, 32, 42]

三、测试验证 #

现在两个递归函数都能正常运行，插入排序输出的有序列表和你二分查找用的测试列表完全一致，你可以直接用排序后的列表作为二分查找的输入进行测试。

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