我们可以使用映射而不是二进制搜索来进行搜索吗？

Question

地图提供 O(1) 查找。难道我们不能遍历数组一次并构建一个对应于它的索引（数组的反面）的映射，当我们想要搜索我们可以调用map[VALUE]的东西时它会返回索引。

它可能不适用于数组中的大值，但假设a[i]<10^5我们不能这样做而不是二进制搜索吗？然后，每个查询将是 O(1)。

PS：我的意思是无序地图..

Answer 1

哈希表，如Python 字典，将给出每次查找的摊销常数平均成本。对于大型数据集，这可能会成为二分查找的一个有趣的替代方法。由于以下原因，某些算法可能绝对需要二分查找：当查找值不在数据集中时，二分查找仍然可以以相同的O(logn)成本判断出数据集中大于查找值的最小值和小于查找值的最大值。对我来说，重复问题不是什么大问题，因为您可以在数组中存储 (value, frequency) 或 (value, [payload1, payload2, ...]) 的元组，因此仍然使用哈希表。

Answer 2

以下是您可能要考虑的问题 -您不能在地图中存储具有相同值的多个元素查找时间是O(log(n))和不是O(1)地图中发生的事情并不神奇，它让我们可以在更短的时间内访问它。有一个散列过程在后台进行，unordered_map这O(1)也需要时间。所以，大 O 隐藏了一个很大的常数时间因素。标准map为您提供O(logn)查找，时间复杂度与数组中的二进制搜索相同。你得到的搜索的平均时间复杂度是差不多的。在 C++ 中使用标准映射的主要问题是它无法保存具有相同值的多个元素。使用 map 可能获得的一个优势是删除和插入时间将是O(logn).因此，如果您知道您将要处理的数据集没有重复元素和/或将频繁添加/删除元素，那么在这种情况下您肯定可以将 map 视为更好的选择

Answer 3

由于确切的运行时间将取决于密钥的长度和类型、它们的分布、它们的数量，因此建议为您的特定应用程序进行基准测试。