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

Question

今天我有一个采访，我被问到如何在数组中搜索一个数字，我说二进制搜索，他问我一个有数千个对象（例如股票）的大数组如何通过股票价格搜索，我又说了二进制搜索，他说在应用二进制搜索之前，对数千个数组进行排序会花费很多时间。

你能耐心等待并教我如何解决这个问题吗？ 谢谢 感谢您的帮助。

Answer 1

我被问到一个类似的问题。扭曲是先搜索排序数组，然后搜索未排序数组。这些是我的答案都没有被接受

1. 对于排序我建议我们可以找到中心并进行线性搜索。二进制搜索也可以在这里工作
2. 对于未分类，我再次建议线性。
3. 然后我建议 Binary 这是错误的。
4. 建议将数组存储在哈希集中并利用哈希。 （因为高空间复杂性城市不被接受）
5. 我推荐了 Tree Set，它是一棵非常适合查找的红黑树。（因为空间复杂度高，所以不被接受）
6. 复制到 Arraylist etch 也被认为是开销。

最后我得到了负面反馈。 虽然我们可能认为以上之一是解决方案，但肯定有一些我缺少的线性搜索的特殊之处。

需要注意的是，在搜索之前进行排序也是一种开销，特别是如果您在两者之间使用任何额外的数据结构。

欢迎任何评论。

Answer 2

我不确定他在想什么。

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

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

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

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

Answer 3

我觉得面试官想让你分析一下数组初始状态在不同情况下，你会用什么算法。当然，你必须知道你可以建立一个哈希表，然后 O(1) 可以找到数字，或者当数组被排序时（排序花费的时间可能会被关注），你可以使用二进制搜索，或者使用其他一些数据结构来完成工作。