为何线性搜索与二分搜索的平均比较次数完全相同？

这是A-Level计算机科学课程中的练习任务，要求修改现有程序，让linearSearch和binarySearch函数每次比较时递增计数变量，并返回该计数；同时创建测试函数对不同长度的列表进行多组测试，输出两者的平均比较次数。但当前代码存在逻辑错误，导致每组测试中两者的平均比较次数完全相同，拆分测试计数变量后问题仍未解决。

原错误代码 #

def linearSearch(searchList, searchVal):
    count = 0
    for i in range(0,len(searchList)):
        count += 1
        if searchList[i] == searchVal:
            return i
    return count

def binarySearch(searchList, searchVal):
    start = 0
    count = 0
    end = len(searchList) - 1
    while start <= end:
        mid = (start + end) // 2
        count += 1
        if searchList[mid] == searchVal:
            return mid
        elif searchList[mid] < searchVal:
            start = mid + 1
        elif searchList[mid] > searchVal:
            end = mid - 1
    return count

def generateList(limit):
    list = []
    for i in range(limit):
        list.append(i)
    return list

import random

def test():
    testType = 1
    while testType <= 5:
        linearTestNo = 0
        binaryTestNo = 0
        length = 10**testType
        searchList = generateList(length)
        linearCountTotal = 0
        binaryCountTotal = 0
        while linearTestNo <= 100 and binaryTestNo <= 100:
            x = random.randint(0,length-1)
            linearCountTotal += linearSearch(searchList, x)
            linearTestNo += 1
            binaryCountTotal += binarySearch(searchList, x)
            binaryTestNo += 1
        print(f"Linear Search took {linearCountTotal/100} comparisons on average for a list of {length} items")
        print(f"Binary Search took {binaryCountTotal/100} comparisons on average for a list of {length} items")
        testType += 1


test()

错误原因 #

核心问题出在两个搜索函数的返回值逻辑上：

• 当找到目标值时，函数返回的是目标元素的索引（linearSearch返回i，binarySearch返回mid），而不是统计的比较次数count。
• 测试中搜索的x都是列表中必然存在的元素（generateList生成连续整数列表，x取0到length-1的随机数），所以每次调用搜索函数都会返回索引值而非比较次数。由于两次搜索的是同一个x，索引值完全相同，最终统计的平均值自然完全一致。

修复后的代码 #

def linearSearch(searchList, searchVal):
    count = 0
    for i in range(len(searchList)):
        count += 1
        if searchList[i] == searchVal:
            return count  # 返回比较次数而非索引
    return count

def binarySearch(searchList, searchVal):
    start = 0
    count = 0
    end = len(searchList) - 1
    while start <= end:
        mid = (start + end) // 2
        count += 1
        if searchList[mid] == searchVal:
            return count  # 返回比较次数而非索引
        elif searchList[mid] < searchVal:
            start = mid + 1
        else:
            end = mid - 1
    return count

def generateList(limit):
    return list(range(limit))  # 简化列表生成逻辑

import random

def test():
    # 遍历5种不同长度的列表
    for testType in range(1, 6):
        length = 10 ** testType
        searchList = generateList(length)
        linearCountTotal = 0
        binaryCountTotal = 0
        test_rounds = 100
        
        # 执行100次测试
        for _ in range(test_rounds):
            x = random.randint(0, length - 1)
            linearCountTotal += linearSearch(searchList, x)
            binaryCountTotal += binarySearch(searchList, x)
        
        # 输出平均比较次数
        print(f"线性搜索在长度为{length}的列表上平均比较次数：{linearCountTotal / test_rounds:.2f}")
        print(f"二分搜索在长度为{length}的列表上平均比较次数：{binaryCountTotal / test_rounds:.2f}")

test()

修复说明 #

1. 修正返回值：将两个搜索函数找到目标时的返回值从索引改为count，确保无论找到与否都返回真实的比较次数。
2. 简化代码：用list(range(limit))替代手动循环生成列表，逻辑更简洁；测试函数改用for循环替代while循环，去掉冗余的计数变量，代码可读性更高。
3. 格式化输出：用.2f格式化平均次数，结果更直观。

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