java - 什么算作二分搜索比较？

Question

我正在编写一个程序，用于确定对给定数字和排序数组运行二分搜索算法所需的比较次数。我不明白什么才算是比较。

// 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，它应该是在数组中查找键时进行的比较的总数。但是什么定义了比较呢？任何时候都有条件吗？

感谢您的帮助，只是想理解这个概念。

Answer 1

通常，每次将键与数组元素进行比较时都会发生比较。不过，代码似乎没有计算在内。它正在计算搜索边界之一(左或右)更改的次数。这并不是完全相同的事情，但它非常接近同一件事，因为边界移动的次数与循环次数直接相关，因此与进行比较的次数直接相关。两种计数方式顶多会相差1或2(我没费心去精确计算)。

另请注意，如果使用通常的定义，则可以重写代码以使用 Integer.compare(int,int)对 key 与 array[mid] 进行一次比较，以确定 key 是否小于、等于或大于 array [中].

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;
}