c# - 二分查找中的比较计数

Question

我接到一项作业，需要计算给定二分查找程序进行的“比较次数”。

问题是二分查找使用 if、else if、else 语句，并且不可能在这些比较之间插入计数器增量语句。

是否有一种设计方法适合记录测试效率的比较？

关于这个 here 还有另一个问题但答案评论说计数器将关闭 1-2 个增量。如果每次检查条件时都进行比较，则将其放在比较主体中是否不准确(仅在为真时才进行评估？)。

在伪代码中我有:

binarysearch(array, k)
   counter = 0;
   x = 0;
   length = array.length

  while (0 <= length)
    int middle = length + x / 2;

     counter+1; 
     if (x is array[middle]) {print(counter) return middle;}
     else if (k < array[middle]) { x = middle - 1; counter + 1; }
     else { x = middle + 1; counter + 1; }

  Print(counter);
  Return -1;

Answer 1

The problem is the Binary Search uses an if, else if, else statement and it's not possible to insert a counter increment statement between these comparisons.

您无法对比较进行计数的断言，因为您无法在 if、else if 和 else 中递增，这是错误的。是的，确实如此，您不能总是按照您想要的方式增加条件语句。尽管你仍然可以数出它们。

举个例子

If(some comparison)
{
   // if we get here we obviously made a comparison and it was true
   Comparisons +=1;
}
else if (some comparison)
{
   // If we get here we obviously made 2 comparisons
   // the first was false, this is true. 
   // However regardless, 2 Comparisons were made 
   Comparisons +=2;
}
else
{
   // if we get here we obviously made 2 comparisons both were false
   // however 2 comparisons were still made 
   Comparisons +=2;
}