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

Question

例如，为什么我们不做 n/3 而不是 n/2

一些数学

使用 n/2 进行二分查找的递推关系是

T(n) = T(n/2) + C 可以简化为

log2(m) = n

和n/3

T(n) = T(n/3) + C 可以简化为

log3(m) = n

所以我的问题是：因为 log3(m) < log2(m) 为什么我们使用 n/2

Answer 1

确实，三元搜索的递归调用比二元搜索少(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

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

Why in a Binary Search do we Divide by 2 and not some other higher constant

recursion

complexity-theory

binary-search

theory

一些数学