关于二元搜索的一个问题

Question

为什么人们通常进行二分搜索而不是三重搜索(每次将数组分成三部分)或者每次甚至分成十部分？

Answer 1

因为二进制搜索导致最小量的比较和查找.对于简单的直觉,考虑每次分成4个部分.

[         |         |    .    |         ]
          v1        v2        v3

您现在已经完成了3次查找,并且必须将您要搜索的最大值与所有三个值进行比较.将其与二次搜索的两次迭代进行比较:

[                   |    .              ]
                    v1
[                   |    .    |         ]
                    v1        v2

您现在已经缩小了相同数量的搜索范围,但只进行了2次查找和2次比较.

Answer 2

这是因为每个级别的1个比较(如在二分搜索中)在任何n元搜索的最坏情况下具有最少的比较数.这是因为每个级别的比较次数线性增加,其中树的深度以对数方式减小.对于n-nary搜索,最坏情况下的比较次数是((n-1)/ log(n))*log(m)其中m是树中项目的数量,其在n = 2时被最小化.