在哪里选择线性搜索而不是二进制搜索 [英] Where to choose linear search over binary search

问题描述

搜索了互联网之后，我无法满足于我发现了一系列综合情况，在这些情况下，线性搜索比二进制搜索更合适。

After having searched the internet I was not able to satisfy myself that I had found a comprehensive set of situations in which a linear search would be preferable to a binary search.

我本质上是想知道是否有可能汇编出相对确定的建议列表（从行业中可能看到的一般编程的角度来看）。另外，如果可以验证我确实已经看到有关该主题的所有内容，我将不胜感激。

I am essentially wondering whether it would be possible to compile a relatively definitive list of advice (from the point of view of general programming as one might find in industry). Alternatively I would much appreciate it if it could be verified that indeed I have seen all there is to say on the subject.

推荐答案

您可能无法提出明确的清单。例如，我前一段时间进行了一些测试，以搜索.NET中的排序列表。对于整数排序的列表，当项数为13时，二进制搜索比顺序搜索要快。对于字符串的排序列表，该数字为8。对于其他比较昂贵的类型，数字为甚至更小。

You probably can't come up with a definitive list. For example, I did some tests a while back with searching sorted lists in .NET. With a sorted list of integers, binary search turned out to be faster than sequential search when the number of items was 13. With a sorted list of strings, that number was 8. With other types for which comparison was more expensive, the number was even smaller.

使用不同的语言或运行时库运行相同的测试将获得不同的数字。它甚至可能取决于内存访问硬件以及其他一些硬件考虑因素。

Running the same test using a different language or runtime library will give you different numbers. It could even depend on the memory access hardware and probably some other hardware considerations.

传统的观点是（也许仍然是）顺序搜索要比二进制搜索简单得多。降低的复杂性使其在小名单上具有很大的优势。今天的事实是，CPU速度和内存访问是如此之快，以至于仅当列表非常很小时，顺序搜索的简单性才是一个因素。

The conventional wisdom was (perhaps still is) that sequential search was so much simpler than binary search that the reduced complexity gave it a large advantage on small lists. The truth today is that CPU speeds and memory access are so fast that the simplicity of sequential search is a factor only when the lists are very small.

最多，您可以提出一组确定的规则，这些规则适用于比较特定数据类型时特定硬件上的一个运行时配置。如果您更改环境或更改数据类型，则必须编写测试以再次对其进行基准测试。

At best you can come up with a definitive set of rules that apply to one runtime configuration on specific hardware when comparing a specific data type. If you change environments or change data types, you have to write tests to benchmark it all over again.

这篇关于在哪里选择线性搜索而不是二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！