map 提供 O(1) 查找。难道我们不能遍历一次数组并构建一个与其索引相对应的映射(与数组相反),当我们想要搜索某些内容时,我们可以调用 map[VALUE]
它将返回索引。
它可能不适用于数组中的大值,但假设 a[i]<10^5
,我们不能用这个来代替二分搜索吗?那么,每个查询的复杂度都是 O(1)。
P.S:我的意思是无序 map ..
最佳答案
一个hash table ,就像 Python 字典一样,将给出每次查找的摊销恒定平均成本。
对于大型数据集,这可能成为二分搜索的有趣替代方案。
由于以下原因,某些算法可能绝对需要二分搜索:
当查找值不在数据集中时,二分查找仍然可以同时知道数据集中大于查找值的最小值和小于查找值的最大值 O(logn) 成本。
对我来说,重复的问题不是什么问题,因为您可以在数组中存储(值,频率)或(值,[有效负载1,有效负载2,...])的元组,因此仍然使用散列表。
关于python - 我们可以使用映射来搜索而不是二分搜索吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62201467/