algorithm - 线性搜索或二分搜索或二分搜索树

Question

我在这里有一个小疑问......

如果我知道列表中的一个搜索元素，比如包含按顺序排序的 32 个元素，出现在前四个位置，

这是最好的搜索算法。

线性搜索至少需要4次迭代....二分查找至少 5 次迭代二叉搜索树怎么样..在这种情况下它会提供更好的解决方案还是等于二分搜索...

我相信线性搜索在这种情况下会更好..

有人可以确认一下吗？

Answer 1

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

此外，对于像这样的少量元素，时间差异可以忽略不计，最好保持简单并进行线性搜索。

您也可以使用 HashTable 或 HashSet 时间复杂度为 O(1)，但话又说回来，对于少量数据，线性搜索可能比执行哈希函数更快。

如果微小的差异真的很重要，我建议在它将运行的环境中对其进行测量。