如何统计二分查找程序中的比较次数？求计数位置指导

问题分析 #

你当前的代码存在两个核心问题：

• 重复调用comparedTo方法却只统计一次比较：当第一个if条件不满足时，else if会再次调用comparedTo，这部分额外的比较没有被计数，导致统计结果偏小。
• 语法逻辑错误：return -1写在了循环内部的else块里，会导致代码无法正常执行到循环结束后的逻辑。

修正后的代码 #

int min = 0;
int max = list.size() - 1;
this->comparisons = 0;
while (max >= min) {
    int middle = (max + min) / 2;
    // 仅调用一次comparedTo，将结果存入临时变量
    int cmpResult = list[middle].comparedTo(key);
    // 每次比较完成后计数+1
    this->comparisons++;
    if (cmpResult == LESS) {
        min = middle + 1;
    } else if (cmpResult == GREATER) {
        max = middle - 1;
    } else {
        // 找到目标元素，返回索引
        return middle;
    }
}
// 循环结束未找到目标，返回-1
return -1;

关键修改说明 #

• 统一比较逻辑：通过临时变量存储comparedTo的结果，确保每次循环只执行一次元素比较，避免重复调用带来的计数遗漏和性能损耗。
• 修正计数时机：在每次执行comparedTo后立即增加计数，保证每一次实际发生的比较都被准确统计。
• 修复语法错误：将return -1移至循环外部，确保当整个搜索范围遍历完毕仍未找到目标时，能正确返回-1。

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