Python实现Binary Search筛选两列表交集文件遇问题求助

你想通过二分查找找出同时存在于list1和list2中的文件名，避免后续列表变大时线性搜索的低效，但当前代码无法完成过滤，问题出在这几个地方：

• 二分查找的前提不满足：二分查找要求目标列表（这里是list2）必须是有序的，如果list2原本无序，直接用二分查找会完全失效。
• 找到匹配后未终止循环：当找到midpoint == fileName时，没有退出while循环，会继续执行后续的二分步骤，可能导致重复添加同一文件到结果列表。
• 逻辑分支覆盖不全：else分支永远不会被触发，因为前面的==、>、<已经覆盖了所有字符串比较的情况，所以new_files_check_list永远不会有内容。
• 语法错误：文件名没有用引号包裹，属于无效字符串；filePath变量未定义，运行时会抛出NameError。

修正后的代码 #

# 修正文件名的字符串格式，定义filePath变量
filePath = "/your/target/path/"
list1 = ["filename1-10-22", "filename2-10-22", "filename3-10-22"]
list2 = ["filename1-9-22", "filename2-9-22", "filename3-9-22", "filename1-10-22", "filename2-10-22", "filename3-10-22"]    

xmls_already_processed_list = []
new_files_check_list = []

# 先确保list2是有序的（如果原本无序，必须先排序）
# 如果list2本身已经有序，可以跳过这一步
list2.sort()

for fileName in list1:
    start = 0
    end = len(list2) - 1
    found = False  # 标记是否找到匹配项
    while start <= end:
        middle = (start + end) // 2
        midpoint = list2[middle]
        if midpoint == fileName:
            xmls_already_processed_list.append((filePath, fileName))
            found = True
            break  # 找到后立即退出循环，避免重复处理
        elif midpoint > fileName: 
            end = middle - 1
        else:  # midpoint < fileName
            start = middle + 1
    # 循环结束后如果没找到，才加入新文件列表
    if not found:
        new_files_check_list.append(fileName)

# 测试输出
print("已处理的文件:", xmls_already_processed_list)
print("新文件:", new_files_check_list)

关键说明 #

1. 排序保证：必须先对list2排序，否则二分查找无法正确工作。如果list2是动态生成的，每次使用前都要确认其有序性。
2. 终止循环：找到匹配项后用break退出while循环，避免不必要的计算和重复添加。
3. 未找到的判断：通过found标记，在循环结束后判断是否未找到，再添加到新文件列表。
4. 语法修正：补全字符串引号和定义缺失的变量，确保代码能正常运行。

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