什么算作二进制搜索比较? [英] What counts as a binary search comparison?

问题描述

我正在编写一个程序，该程序确定对给定的数字和排序后的数组运行二进制搜索算法需要进行多少次比较.我不明白的是什么才是比较.

I'm writing a program that determines how many comparisons it takes to run a binary search algorithm for a given number and sorted array. What I don't understand is what counts as a comparison.

// returns the number of comparisons it takes to find key in sorted list, array
  public static int binarySearch(int key, int[] array) {
    int left = 0;
    int mid;
    int right = array.length - 1;
    int i = 0;
    while (true) {
      if (left > right) {
        mid = -1;
        break;
      }
      else {
        mid = (left + right)/2;
        if (key < array[mid]) {
          i++;
          right = mid - 1;
        }
        else if (key > array[mid]) {
          i++;
          left = mid + 1;
        }
        else {
          break; // success
        }
      }
    }
    return i;
  }

该函数返回i，这应该是在查找数组中的键时进行比较的总数.但是，什么定义了比较?有条件吗?

The function returns i, which is supposed to be the total number of comparisons made in finding the key in array. But what defines a comparison? Is it any time there is a conditional?

感谢您提供任何帮助，只是试图了解这个概念.

Thanks for any help, just trying to understand this concept.

推荐答案

通常，每次将键与数组元素进行比较时，都会进行比较.但是，该代码似乎并未对此进行计数.它计算一个搜索边界(left或right)之一被更改的次数.计数的对象并不完全相同，但是非常接近同一件事，因为边界移动的次数与循环的次数直接相关，因此与进行比较的次数直接相关.最多，这两种计数方式将相差1或2(我不必理会确切的数字).

Usually, a comparison occurs each time the key is compared to an array element. The code seems to not be counting that, though. It is counting how many times one of the search boundaries (left or right) is changed. It's not exactly the same thing being counted, but it's pretty close to the same thing, since the number of times a boundary is shifted is directly related to the number of times through the loop and hence to the number of times a comparison is made. At most, the two ways of counting will be off by 1 or 2 (I didn't bother to figure that out exactly).

还请注意，如果要使用通常的定义，则可以将代码重写为使用

Note also that if one were to use the usual definition, the code could be rewritten to use Integer.compare(int,int) do a single comparison of key with array[mid] to determine whether key was less than, equal to, or greater than array[mid].

public static int binarySearch(int key, int[] array) {
    int left = 0;
    int mid;
    int right = array.length - 1;
    int i = 0;
    while (left <= right) {
        mid = (left + right)/2;
        int comp = Integer.compare(key, array[mid]);
        i++;
        if (comp < 0) {
            right = mid - 1;
        }
        else if (comp > 0) {
            left = mid + 1;
        }
        else {
            break; // success
        }
    }
    return i;
}

这篇关于什么算作二进制搜索比较?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！