为什么使用暴力搜索排序列表对于硅谷的演员来说很有趣

Question

在《硅谷》节目第 06 季第 4 集中，一位程序员因为“暴力破解排序列表”而被取笑。您可以看到下面代码的屏幕截图。

据我了解，如果在排序列表中找到“元素”，代码将返回“索引”。如果不是，它只会返回-1。这是对所有元素的基本比较（他们觉得很有趣）

为什么他们觉得好笑？我不明白。

Answer 1

二分查找用于排序列表，因为它利用了列表递减或递增的特性。

可以对任何列表进行暴力破解，无论是否排序。

O(n)vsO(log(n))也会导致巨大的性能差异。

考虑一个包含 1000000 个元素的列表，那么这需要 1000000 个循环，在二分搜索中只需要大约 lg2(1000000) ~= 20 （成本稍高）循环。

Answer 2

考虑一个包含 1000000 个元素的列表，那么这需要 1000000 个循环，在二分搜索中只需要大约 lg2(1000000) ~= 20 （成本稍高）循环。

对于原始循环，绝对时间可能约为 3-4ns，对于二进制循环，绝对时间可能约为 100-150ns（许多缓存未命中和 50% 分支预测未命中），因此 3000000-4000000ns 到 2000-3000ns。