二分查找比较计数器

Question

所以，我有一个二进制搜索代码（不是我的），但我不知道如何将计数器放在它进行了多少次比较上。输入元素然后排序。然后这个代码来了。    System.out.println("\nEnter value to find");    num_search = in.nextInt();    first  = 0;    last   = n - 1;    middle = (first + last)/2;     while( first <= last )    {       if ( a[middle] < num_search )        first = middle + 1;          else if ( a[middle] == num_search )     {       System.out.println(num_search + " found at location " + (middle + 1) + ".");          System.out.println("Counter = " + (ctr + middle));        break;      }      else     last = middle - 1;      middle = (first + last)/2;    }    if (first > last)  System.out.println(num_search + " isn't present in the list.\n");

Answer 1

简单地增加ctr所有三种情况的值。确保您已初始化ctrwith 0;

while( first <= last )

    { 

      if ( a[middle] < num_search )

        {first = middle + 1;

        ctr++; //<----increment the count by 1

        }

      else if ( a[middle] == num_search )

     {

       ctr++; //<----increment the count by 1

       System.out.println(num_search + " found at location " + (middle + 1) + ".");

       System.out.println("Counter = " + ctr); //<-----add 1 to result

       break;

      }

      else

      {last = middle - 1;

      ctr++; //<----increment the count by 1

      }

      middle = (first + last)/2;

    }

    if (first > last)

        System.out.println(num_search + " isn't present in the list.\n");

Answer 2

您可以像这样增加计数：

int count = 0;

while( first <= last )

{ 

  if ( a[middle] < num_search ) {

    count+= 1;

    first = middle + 1;  

  }  

  else if ( a[middle] == num_search )

 {

   count+= 2;

   System.out.println(num_search + " found at location " + (middle + 1) + ".");

    break;

  }

  else {

      count+= 3;

     last = middle - 1;

 }

  middle = (first + last)/2;

}

System.out.println("Counter = " + count);