什么是可以在未排序数组上进行的最快搜索?

是的,如果不对数据进行排序,线性搜索就可以做到最好。

对于一个真正随机的非排序数组,线性搜索是最好的方法。

如果可以假定数据是粗略排序的,那么您可能能够更好地使用某种启发式方法。

线性地。或者对数组进行排序并在日志时间搜索。

如果没有对数组进行排序,就没有任何优化可以完成。所有的优化都取决于对阵列的某种了解是否得到保证。如果没有这个,你就不能假设任何事情,必须对每一个项目进行线性检查。

正如其他人所提到的,线性搜索是前进的道路。但是,根据您的设置,以下内容可能与加快速度有关,也可能与加快速度无关。

如果某些项目的搜索频率高于其他项目,那么一个小的缓存可能会很有用。例如,如果您正在为文件系统实现lookup()操作(其中数据最终存储在磁盘的某个地方),缓存可以提供极大的帮助。

您是否可以对数据进行排序/筛选,以便最常见的查找项位于数组的开头附近?

将数据存储在两组中是否可行?一个已排序,一个未排序?排序后,您应该能够快速搜索您的项目。如果找不到,请转到未排序的列表并通过该列表进行线性搜索。为什么?虽然您说过在每次插入后插入是不实际的,但是定期从未排序列表插入排序列表是否实际/有效?

它必须都在一个未排序的数组中吗?你能把你的数据放到分类数据块中吗?也就是说,每个块可能有1000个排序条目。搜索每个排序块可能比搜索整个未排序列表更快。

只是一些想法。它们可能不适用于您的情况,但希望它们对您有所帮助。

优化线性搜索有一些聪明的方法,但最终没有一种方法能真正提高性能,但会使代码容易出错,并且难以理解。因此,我建议坚持简单的线性搜索(即简单的迭代+比较)。

一旦您的代码显示了一个未排序的列表,是的,您将需要进行线性搜索。

但是,如果要多次搜索,您可以做一些事情。

当然,首先要对列表进行排序。这将使第一次查找花费相当长的时间,但随后的查找将更快。

其次,我建议缓存结果。对于大多数用法,我发现后面的查找有很高的可能性,要么是相同的值,要么是附近的值。

不过,您不应该为这两个问题操心,除非列表非常大并且搜索速度很慢。一般来说, 你写的代码越少,每个人的境况就越好。 .

如果可以,可以考虑首先更改数据的存储/创建方式。与其向数组中添加项,不如创建一个完整的二叉树(或其他)并使用它。它使操作数据的速度稍慢一些,但它不应该像每次重新排序数据那样慢,而且会使搜索速度更快。