java - 为什么在二分查找中使用中间表达式的上限值是错误的？

Question

在典型的二分搜索算法中(例如在 Java 中)，我们使用除法的下限而不是上限来找到中间元素的选择:

public static void binarySearch(int[] array, int lowerbound, int upperbound, int key)
{
  int comparisonCount = 0;    // counting the number of comparisons (optional)        
  while (lowerbound <= upperbound)
  {
    final int position = (lowerbound + upperbound) / 2;
    ++comparisonCount;
    if (array[position] == key)
    {
      System.out.println("The number was found in array subscript " + position + '.');
      System.out.println("The binary search found the number after " + comparisonCount +
                         " comparisons.");
      return;
    }
    if (array[position] > key)             // If the number is > key, ..
    {                                      // decrease position by one. 
      upperbound = position - 1;   
    }                                                             
    else                                                   
    {                                                        
      lowerbound = position + 1;           // Else, increase position by one. 
    }
  }
  System.out.println("Sorry, the number is not in this array. The binary search made "
                     + comparisonCount  + " comparisons.");
}

此处的位置公式使用向下舍入的整数除法(例如，3.5 变为 3)。我的教授说四舍五入的替代方案将导致错误。如果是这样，那是什么？为什么该值必须向下舍入而不是向上舍入？

Answer 1

假设序列中只有一个元素需要搜索。您的下限为零，上限为一，因为边界表示半开放范围。它具有从上限减去下限的属性，得出序列的长度。

如果下限为零且上限为 1，并且您计算表达式

(ceiling (+ lower-bound upper-bound) 2)

你得到一个，它不是这个序列中单个元素的有效索引。唯一有效的索引是零，这是更常规的表达式

(floor (+ lower-bound upper-bound) 2)

会产生。

如果您有三个元素，其中中间元素的索引显然为 1，请再次考虑这一点

(ceiling (+ 0 3) 2)

等于二，这是最后元素的索引，而不是中间元素。

我们可以通过询问如此糟糕的中间元素选择是否最终仍会产生正确的答案来进一步探讨您的问题。该算法仍然会朝着正确的方向徘徊到正确的元素(或者是该元素所属的位置，如果序列中不存在)，但是当所考虑的子序列缩小到只有一个元素时，该算法将再次失败，因为它会错误地选择一个比剩余元素大一的索引。