如何在大数组中搜索对象？

Question

我今天接受了一次采访,有人问我是如何搜索数组中的数字的,我说二元搜索,他问我一个有数千个对象(例如股票)的大数组如何搜索例如股票的价格,我再说二进制搜索,他说在应用二进制搜索之前,对数千个数组进行排序会花费很多时间.

你能和我一起去教我怎么解决这个问题吗？谢谢你的帮助表示赞赏.

Answer 1

我不确定他的想法。

如果你只想一次找到数字，并且不能保证数组是否已排序，那么我认为你无法击败线性搜索。平均而言，在找到值之前，您需要在数组中查找一半，即预期运行时间 O(N)；排序时，您必须至少接触每个值一次，甚至可能不止一次，即预期运行时间 O(N log N)。

但如果您需要查找多个值，那么花在排序上的时间很快就会得到回报。使用排序数组，您可以在 O(log N) 时间内进行二分搜索，因此如果您投入时间进行排序，那么在第三次搜索时您肯定会领先。

如果允许您构建不同的数据结构来帮助解决问题，您可以做得更好。您可以构建某种索引，例如哈希表；但解决此类问题的最佳数据结构可能是某种树结构。然后，您可以比追加新值并重新排序数组更快地将新值插入到树中，并且查找任何值的查找时间仍然是 O(log N)。有不同类型的树可用：二叉树、B 树、trie 等。

但正如 @Hot Licks 所说，哈希表通常用于此类事情，并且更新起来非常便宜：您只需在主数组上附加一个值，然后更新哈希表以指向新值。哈希表的时间非常接近 O(1)，这是你无法超越的。（如果没有哈希冲突，哈希表的复杂度为O(1)；假设有一个好的哈希算法和足够大的哈希表，则几乎不会发生冲突。我认为你可以说哈希表的复杂度为 O(N)，其中 N是每个“桶”的平均哈希冲突数。如果我的观点是错误的，我希望很快就能得到纠正；这是 StackOverflow！）