在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

试试这样的东西：

 binarysearch(array, k)

   counter = 0;

   x = 0;

   length = array.length

   while (0 <= length)

    int middle = length + x / 2;

     if ((++counter>0) and x is array[middle]) {print(counter) return middle;}

     else if ((++counter>0) and k < array[middle]) { x = middle - 1; }

     else { x = middle + 1; }

  Print(counter);

  Return -1;

（++ counter> 0）始终为true，并且不要更改if条件