线性搜索或二进制搜索或二叉搜索树

如果我知道，在列表中搜索元素，比如包含顺序排序32个元素，首先是四个位置中出现，

这是最好的搜索算法。

线性搜索至少需要4次迭代.... 二进制搜索至少5次迭代如何二叉搜索树..没有给出更好的解决方案在这种情况下或等于二分查找...

我相信线性搜索会更适合这种情况..

有人可以证实这一点吗？

2011-10-05 user976027

如果您知道位置在前4个位置，而线性搜索更好，因为您必须测试不超过4个元素。使用二进制搜索lg 32 = 5，所以你将不得不测试最多5个元素。

此外，对于少量这样的元素，时间差异可以忽略不计，您可以通过保持简单并进行线性搜索来获得最佳服务。

对于O（1）时间，您可能也可以使用HashTable或HashSet，但对于少量数据，线性搜索可能会比执行散列函数更快。

如果这个小的差别确实很重要，我会建议在它运行的环境中测量它。

2011-10-05 06:20:18 spatulamania

什么关于二叉搜索树？它与二分查找相似吗？ – user976027

是的，二叉搜索树是围绕二进制搜索进行设计的数据结构。一个二叉搜索树比一个已排序数组的优点是插入和删除元素。查找时间（给定树是平衡的）是相同的。 – spatulamania

你可以对前4个元素进行二分搜索。它将是lg 4 = 2次迭代！ :-)

2011-10-05 06:23:28 Aliza

谢谢你..搜索必须做的所有元素..只有少数我会知道它将在前4个元素 – user976027

有了这么多的元素和具体的应用程序，二叉搜索树会是一个矫枉过正的问题。

此外，为了解决目前的问题，线性搜索会更好，因为定位特定元素的预期迭代次数将超过二进制搜索。

对于现实生活场景，这样呈现的问题将非常罕见。因此，在排序的数组上使用二进制搜索总是更好。

2011-10-05 06:24:22

如果数据以某种方式均匀分布，则使用插值搜索是明智的。通过使用分配知识，您有一个很好的机会在一个步骤中猜测正确的位置。预期的复杂度是O（log（log（n）））。

这里是我的网页，在那里我有在Java中实现的算法链接：Algoritmy.net - interpolation search implementation

2011-10-05 20:11:31 malejpavouk

回答