Python 3.6二分查找函数隐藏测试失败，求排查逻辑问题

我正在为学校作业编写名为binary_simple_plate_finder的二分查找函数，自己测试时运行正常，但提交到作业系统后大部分隐藏测试都失败了。补充说明：stolen_plates列表是有序的，自用测试用例没问题，但肯定有遗漏的情况。

原函数代码 #

def binary_simple_plate_finder(stolen_plates, sighted_plates):

    result_list = []
    
    total_comparisons = 0
    for plate in sighted_plates:
        middle = (len(stolen_plates) - 1) // 2
        right = (len(stolen_plates) - 1)
        left = 0
        finished = False
        while not finished:
            if plate == stolen_plates[middle]:
                total_comparisons = total_comparisons + 1
                result_list.append(plate)
                finished = True
            elif left == right and plate != stolen_plates[middle]:
                total_comparisons = total_comparisons + 1
                finished = True            
            elif plate > stolen_plates[middle]:
                total_comparisons = total_comparisons + 1
                left = middle + 1
                middle = ((left + right) // 2)
            elif plate < stolen_plates[middle]:
                total_comparisons = total_comparisons + 1
                right = middle - 1
                middle = ((left + right) // 2)
            
    return result_list, total_comparisons

stolen = ["ABJ603", "BADMON", "CHUD69", "CRAP22", "DENGEL", "EFFETE", "IMGAY", "NINGAS", "OKEDOK", "PUS556", "ZMAN21"]
sighted = ["OKEDOK", "ABJ603", "BASTAR", "NINGAS"]
print(binary_simple_plate_finder(stolen, sighted))

问题分析 #

你的二分查找逻辑有两个关键漏洞，导致边界场景下出错：

• 未处理left > right的情况：当查找的元素不在列表中，且left超过right后，计算middle会得到负数或无效索引，触发错误判断甚至数组越界。比如查找比所有元素都大的元素时，left会持续右移，最终超出有效范围。
• 循环终止条件不严谨：当前只判断了left == right且不匹配的情况，但当left > right时，循环仍会继续执行，导致无效的数组访问。

修复后的代码 #

def binary_simple_plate_finder(stolen_plates, sighted_plates):
    result_list = []
    total_comparisons = 0
    for plate in sighted_plates:
        left = 0
        right = len(stolen_plates) - 1
        found = False
        while left <= right:
            middle = (left + right) // 2
            total_comparisons += 1
            if plate == stolen_plates[middle]:
                result_list.append(plate)
                found = True
                break
            elif plate > stolen_plates[middle]:
                left = middle + 1
            else:
                right = middle - 1
    return result_list, total_comparisons

# 扩展测试用例，覆盖边界场景
stolen = ["ABJ603", "BADMON", "CHUD69", "CRAP22", "DENGEL", "EFFETE", "IMGAY", "NINGAS", "OKEDOK", "PUS556", "ZMAN21"]
sighted = ["OKEDOK", "ABJ603", "BASTAR", "NINGAS", "ZMAN22", "AAAAAA"]
print(binary_simple_plate_finder(stolen, sighted))

修复说明 #

• 调整循环终止条件：用left <= right作为循环判断标准，当left超过right时，直接终止循环，避免无效索引访问。
• 优化middle计算时机：每次循环开始时计算middle，确保基于当前有效范围，避免提前计算导致的错误。
• 简化逻辑：去掉冗余的finished标志，找到匹配项直接break，未找到则循环自然结束，代码更简洁。
• 覆盖边界场景：能正确处理查找比所有元素大/小的元素、单个元素列表、空列表（若作业允许）等情况。

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