为什么在二进制搜索中我们要除以2而不是其他更高的常数

的确,三元搜索比二元搜索具有更少的递归调用 (log3(m) < log2(m)) 然而,在最坏的情况下,三元搜索比二元搜索具有更多的比较。

为了进一步检查,让我们比较一下C语言中的二元和三元搜索算法++

二进制搜索

// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
      int mid = l + (r - l)/2;

      // If the element is present at the middle itself
      if (arr[mid] == x)  return mid;

      // If element is smaller than mid, then it can only be present
      // in left subarray
      if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);

      // Else the element can only be present in right subarray
      return binarySearch(arr, mid+1, r, x);
   }

   // We reach here when element is not present in array
   return -1;
 }

三元搜索

// A recursive ternary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int ternarySearch(int arr[], int l, int r, int x)
{
   if (r >= l)
   {
        int mid1 = l + (r - l)/3;
        int mid2 = mid1 + (r - l)/3;

        // If x is present at the mid1
        if (arr[mid1] == x)  return mid1;

        // If x is present at the mid2
        if (arr[mid2] == x)  return mid2;

        // If x is present in left one-third
        if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);

        // If x is present in right one-third
        if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);

        // If x is present in middle one-third
        return ternarySearch(arr, mid1+1, mid2-1, x);
   }
   // We reach here when element is not present in array
   return -1;
}

在最坏的情况下,二进制搜索可以 2log2(n) + 1 三元搜索的比较 4log3(n) + 1

这些比较归结为 log2(n) 和 2log3(n)

2log3(n) = (2 / log2(3)) * log2(n)

自从 (2 / log2(3)) > 1 在最坏的情况下,Ternay搜索会进行更多的比较

Source