二分查找代码返回None问题排查及Python免费算法课程推荐

问题原因 #

你的二分查找分支逻辑写反了：当中间值小于目标值时，目标应该在右半区间，需要将start_index更新为midpoint+1；但你错误地把end_index设为midpoint-1，导致搜索范围被错误缩小，最终无法找到目标值，函数因没有匹配到return语句，默认返回None。

比如查找列表中的8时，第一次计算的midpoint是3（对应值4），4<8，此时本该往右半区搜索，但你的代码直接把end_index改成2，搜索范围变成[0,2]，彻底跳过了包含8的右半部分，循环结束后无有效返回，所以输出None。

修正后的代码 #

def binary_search(lst, target):  # 避免用list做变量名，和内置类型冲突
    start_index = 0
    end_index = len(lst) - 1
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        midpoint_value = lst[midpoint]
        if midpoint_value == target:
            return midpoint + 1  # 此处返回的是从1开始计数的位置，若要索引则改为return midpoint
        elif midpoint_value < target:
            start_index = midpoint + 1  # 正确逻辑：目标在右半区，更新起始索引
        else:
            end_index = midpoint - 1  # 目标在左半区，更新结束索引

print(binary_search([1,2,3,4,5,6,7,8],8))  # 输出8（对应索引7+1）

注：数字8位于列表的第7个索引位置（从0开始计数）

• 北京大学《数据结构与算法》MOOC：系统讲解数据结构基础和经典算法，包含Python实现案例，全程免费
• 菜鸟教程Python算法板块：文字类教程，覆盖链表、树、排序、查找等常用内容，适合快速查阅和入门
• Python官方文档：查看标准库collections等模块的说明，了解内置数据结构的实现原理
• B站免费算法系列视频：比如UP主“代码随想录”的Python算法入门合集，从基础题到进阶题，讲解细致

内容的提问来源于stack exchange，提问作者Muhammad Mu'aaz Ansari