algorithm - 我如何证明线性搜索比当前情况下的二进制更快？

Question

我有一个排序的元素列表：

c f g o p q r t w 

我需要f使用二进制搜索来查找元素，我做到了。我还在 2 个比较中使用线性搜索找到了这个元素。现在我需要证明在这种情况下线性比二进制快，我该怎么做？谢谢！

Answer 1

计算每个算法所需的操作。大致来说，二分查找需要：

• 计算中点 = 5
• 比较“p”和“f”
• 计算中点 = 3
• 比较“g”和“f”
• 计算中点 = 2
• 比较“f”和“f”——成功

大约 6 次操作。

另一方面，线性搜索只需要：

• 比较“c”和“f”
• 比较“f”和“f”——成功

如果您认为有必要包括索引计算以遍历列表，则线性搜索仍然更快：

• 我=1
• 比较“c”和“f”
• 我=2
• 比较“f”和“f”——成功

Answer 2

执行这两种情况，并计算每种情况的操作次数。二分查找会更大。

Answer 3

下面我假设搜索的元素存在于数组中。在最坏的情况下，二分搜索需要 log ₂ (N) 次迭代才能找到所需的元素。平均情况接近那个。线性搜索平均需要 N/2 次迭代才能找到元素。

迭代是二分查找通常包括 3-4 个步骤：计算中间索引、取中间元素和最多两次比较。因此，使用二进制搜索的平均搜索将花费 log ₂ (N) * 3.5 步。

在线性搜索中，它需要两个操作——在当前索引处获取元素值和比较。平均而言，线性搜索需要 N * 2 / 2 = N 步。

在您的情况下，我们有 log ₂ (9) * 3.5 = 3.1 * 3.5 = 10.85 步进行二分搜索。以及线性搜索的 9 个步骤。

因此，在 9 大小的数组上，线性搜索平均起来似乎稍微快一些，但不是很快。在更大的数组上，二分搜索很容易胜过线性搜索。