关于二进制搜索的一个问题 [英] one question about binary search

问题描述

为什么人们通常执行二进制搜索而不是三次搜索（每次将
数组分成三部分），或者甚至每次分成十部分？

Why people usually do binary search instead of triple search (divide the array into three parts each time) or even divide into ten parts each time?

推荐答案

这是因为在所有n元搜索的最坏情况下，每级1个比较（如在二进制搜索中）的比较次数最少。这是因为每级比较的次数线性增加，而树的深度则对数减少。对于n元搜索，比较的最坏情况是（（n-1）/ log（n））* log（m），其中m是树中的项目数，在n = 2时被最小化。

Its because 1 comparison per level (as in binary search) has the least number of comparison in the worst case of any n-ary search. This is because the number of comparisons per level increases linearly where the depth of the tree decreases logarithmically. For n-nary search the worst case number of comparisons is ((n-1)/log(n)) *log(m) where m is the number of items in the tree, which is minimized at n=2.

这篇关于关于二进制搜索的一个问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！