在哪里选择线性搜索而不是二进制搜索

本文介绍了在哪里选择线性搜索而不是二进制搜索的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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.