如果有三元搜索，为什么要使用二分搜索? [英] Why use binary search if there's ternary search?

问题描述

我最近听说过三元搜索，我们将数组分成 3 部分并进行比较.这里会有两个比较，但它将数组减少到 n/3.为什么人们不使用这么多?

I recently heard about ternary search in which we divide an array into 3 parts and compare. Here there will be two comparisons but it reduces the array to n/3. Why don't people use this much?

推荐答案

实际上，人们确实将 k-ary 树用于任意 k.

Actually, people do use k-ary trees for arbitrary k.

然而，这是一种权衡.

要在 k-ary 树中查找元素，您需要进行 k*ln(N)/ln(k) 运算(记住基数变化公式).您的 k 越大，您需要的整体操作就越多.

To find an element in a k-ary tree, you need around k*ln(N)/ln(k) operations (remember the change-of-base formula). The larger your k is, the more overall operations you need.

您所说的逻辑扩展是为什么人们不对 N 个数据元素使用 N 叉树?".当然，这将是一个数组.

The logical extension of what you are saying is "why don't people use an N-ary tree for N data elements?". Which, of course, would be an array.

这篇关于如果有三元搜索，为什么要使用二分搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！