问哪里可以选择线性搜索而不是二进制搜索

EN

我选择线性搜索而不是二进制搜索的原因如下：

1. 列表未排序，只需搜索一次。
2. 这个列表很小(尽管这本身就是一个模糊的概念--我读过的元素还不到100个？)
3. 列表将需要在搜索操作之后进行排序(例如插入)，因为诉诸将主导整个任务的时间复杂性。
4. 数据结构不是随机访问(如链接列表)。
5. 没有任何数据可以帮助搜索(相对接近？)

你可能想不出一个确定的名单。例如，我在.NET中对排序列表进行了一段时间的测试。使用排序的整数列表，当条目数为13时，二进制搜索比顺序搜索速度更快。对于排序的字符串列表，该数字为8。对于其他类型，比较比较更昂贵，搜索的数量甚至更小。

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

传统的观点是(也许仍然如此)，顺序搜索比二进制搜索要简单得多，因此减少的复杂性使它在小列表上有了很大的优势。今天的事实是，CPU速度和内存访问速度如此之快，只有当列表非常小时，顺序搜索的简单性才是一个因素。

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