在互联网上搜索后，我无法让自己满意，因为我发现了一组全面的情况，在这些情况下，线性搜索比二分搜索更可取。
我基本上想知道是否有可能编制一份相对明确的建议列表（从工业中可能发现的一般编程的角度来看）。或者，如果可以证实我确实已经看到了有关该主题的所有内容，我将不胜感激。
问问题
9232 次
2 回答
1
你可能无法拿出一个明确的清单。例如，不久前我做了一些测试，在 .NET 中搜索排序列表。对于整数的排序列表，当项目数为 13 时，二进制搜索比顺序搜索更快。对于字符串的排序列表，该数字为 8。对于比较昂贵的其他类型，该数字为更小。
使用不同的语言或运行时库运行相同的测试会给你不同的数字。它甚至可能取决于内存访问硬件以及可能的其他一些硬件考虑因素。
传统观点认为（也许现在仍然如此）顺序搜索比二分搜索简单得多，因此降低的复杂性使其在小型列表上具有很大优势。今天的事实是 CPU 速度和内存访问如此之快，以至于顺序搜索的简单性仅在列表非常小时时才是一个因素。
在比较特定数据类型时，您最多可以提出一套明确的规则，适用于特定硬件上的一个运行时配置。如果您更改环境或更改数据类型，则必须编写测试以重新进行基准测试。
于 2014-03-21T19:44:36.653 回答
1
我选择线性搜索而不是二分搜索的原因列表如下：
该列表未排序，只能搜索一次
列表很小（尽管这本身就是一个模糊的概念——我读过的元素不到 100 个？）
该列表将需要在搜索操作之后进行排序（由于插入），因为重新排序将主导整个任务的时间复杂度
数据结构不是随机访问（如链表）
不知道可以帮助搜索的数据（相对接近度？）
于 2014-03-21T17:31:56.703 回答