在Binary Search中计数比较

Question

给我一个作业，我需要计算给定的Binary Search程序进行的“比较次数”。

问题是二进制搜索使用了if，else，if，else语句，并且无法在这些比较之间插入计数器增量语句。

有没有适合的设计方法来保持比较计数以测试效率？

有一个关于这个另一SO问题在这里得到的答复意见计数器将关闭1-2增量。如果每次检查条件时都进行比较，则将其放置在比较主体中是否不准确（只有在为true时才进行评估？）。

用伪代码，我有：

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

试试这样的东西：&nbsp;binarysearch(array, k)&nbsp; &nbsp;counter = 0;&nbsp; &nbsp;x = 0;&nbsp; &nbsp;length = array.length&nbsp; &nbsp;while (0 <= length)&nbsp; &nbsp; int middle = length + x / 2;&nbsp; &nbsp; &nbsp;if ((++counter>0) and x is array[middle]) {print(counter) return middle;}&nbsp; &nbsp; &nbsp;else if ((++counter>0) and k < array[middle]) { x = middle - 1; }&nbsp; &nbsp; &nbsp;else { x = middle + 1; }&nbsp; Print(counter);&nbsp; Return -1;（++ counter> 0）始终为true，并且不要更改if条件