有没有比二分搜索更快的算法来搜索数组的排序值？
就我而言，我在一个数组中有一个排序值（可以是任何类型的值），如果我正在寻找的值在范围内A，我需要返回nA[n] and A[n+1]
问问题
32872 次
12 回答
43
如果值是整数，则可以比 O(log n) 做得更好，在这种情况下，就 n 而言，您可以实现的最佳最坏情况运行时间是 O(sqrt(log n))。否则，除非输入序列中有模式，否则无法击败 O(log n)。在整数的情况下，有两种方法可以击败 O(log n)。
首先，您可以使用 y-fast 树，它通过将所有前缀存储在哈希表中来工作，您要为其存储至少一个具有该前缀的整数。这使您能够执行二进制搜索以查找最长匹配前缀的长度。这使您能够在 O(log w) 时间内找到要搜索的元素的后继元素，其中 w 是单词中的位数。尽管有一些细节可以使这项工作发挥作用并且仅使用线性空间，但它们并不算太糟糕（请参阅下面的链接）。
其次，您可以使用融合树，它使用位技巧使您能够在恒定数量的指令中执行 w^O(1) 比较，产生 O(log n / log w) 的运行时间。
这两种数据结构之间的最佳权衡发生在 log w = sqrt(log n) 时，运行时间为 O(sqrt(log n))。
有关上述内容的详细信息，请参见 Erik Demaine 课程的第 12 和 13 讲：http: //courses.csail.mit.edu/6.851/spring07/lec.html
于 2010-10-30T05:23:39.673 回答
6
一种可能性是将其视为寻找函数的根。基本上，发现：
a[i] <= i <= a[i + 1]
相当于：
a[i] - i <= 0 <= a[i + 1] - i
然后你可以试试牛顿法之类的东西。这些类型的算法在工作时通常比二分搜索收敛得更快，但我不知道有一种算法可以保证对所有输入都收敛。
于 2010-10-30T04:53:51.010 回答
5
是和不是。是的，平均而言，有些搜索比二等分搜索更快。但我相信它们仍然是 O(lg N)，只是常数较低。
您希望最大限度地减少查找元素所花费的时间。通常，希望使用更少的步骤，一种方法是最大化将在每个步骤中消除的预期元素数量。使用二分法，总是正好有一半的元素被消除。如果您对元素的分布有所了解，您可以做得比这更好。但是，选择分区元素的算法通常比选择中点更复杂，而且这种额外的复杂性可能会压倒您期望通过使用更少的步骤而节省的时间。
确实，在这样的问题中，攻击二阶效应（如缓存局部性）比搜索算法更好。例如，在进行重复的二分搜索时，相同的几个元素（第一、第二和第三四分位数）被非常频繁地使用，因此将它们放在单个缓存行中可能远远优于随机访问列表。
将每个级别划分为 4 或 8 个相等的部分（而不是 2 个）并通过这些进行线性搜索也可能比二等分搜索更快，因为线性搜索不需要计算分区并且还具有更少的数据依赖性，可以导致缓存停止。
但所有这些仍然是 O(lg N)。
于 2010-10-30T04:46:30.777 回答
5
如果列表中的值是均匀分布的，那么您可以尝试加权拆分而不是二进制拆分，例如，如果所需值是从当前下限到当前值的三分之一，那么您可以尝试以下元素也是三分之一。但是，这可能会在值聚集在一起的列表中受到严重影响。
于 2010-10-30T04:46:49.870 回答
5
下面的算法呢？它被称为指数搜索，是二分搜索的变体之一。 http://en.m.wikipedia.org/wiki/Exponential_search
在大小为 n 的已排序数组 A 中搜索元素 k。查找 A[2^i] for i=0, 1, 2,... 直到超出 k 在 A 中的位置。然后对数组左侧（小于）i 的部分进行二进制搜索。
int exponential_search(int A[], int key)
{
// lower and upper bound for binary search
int lower_bound = 0;
int upper_bound = 1;
// calculate lower and upper bound
while (A[upper_bound] < key) {
lower_bound = upper_bound;
upper_bound = upper_bound * 2;
}
return binary_search(A, key, lower_bound, upper_bound);
}
该算法将在 O(log idx) 上运行，其中 idx 是 A 中 k 的索引。（两个 stpes 都在 log idx 中）。在最坏的情况下，算法在 O(log idx) 中，如果 k 是 A 的最大元素之一或大于 A 的任何元素。乘法常数大于二分搜索，但算法会在非常大的情况下运行得更快数组以及查找数组开头的数据时。
我想知道这个算法比二分搜索更可取的最小大小 n，但我不知道。
于 2013-09-04T14:56:45.597 回答
2
首先，在进行优化之前进行测量。
您真的需要优化该搜索吗？
如果是这样，那么其次，首先考虑算法复杂性。例如，您可以使用树（例如 a std::map）而不是数组吗？如果是这样，那么它取决于插入/删除与搜索的相对频率，但是手头有一个排序数组的前提表明，与数据集更改相比，搜索是频繁的，因此做一些额外的工作是有意义的插入/删除，使每次搜索更快——即对数时间。
如果您发现搜索时间确实是需要解决的瓶颈，并且不，不可能更改数据表示，并且列表很短，那么线性搜索通常会更快，因为它每次比较所做的工作更少。
否则，如果列表更长，并且没有已知或假定值的特定分布，并且值不能被视为数字，并且内存消耗应该是恒定的（例如，排除构造哈希表），那么二进制搜索每次比较产生 1 位信息，这可能是您第一次搜索所能做的最好的事情。
干杯&hth。
于 2010-10-30T06:04:08.007 回答
1
您总是可以将它们放在哈希表中，然后搜索将是 O(1)。虽然这将是内存密集型的，如果您继续添加项目，则可能需要重新存储哈希表。重新分桶是 O(n)，但它会摊销到 O(1)。这基本上取决于您是否能负担得起该空间和潜在的缓存未命中。
于 2010-10-30T04:46:48.897 回答
1
杂项评论中提到了它，但我认为对这个特定问题（“任何类型，数组中的值”）的自然而简单的答案将是插值搜索：
插值搜索不计算中点，而是估计目标值的位置，同时考虑数组中的最低和最高元素以及数组的长度。它的工作原理是在许多情况下，中点不是最好的猜测。例如，如果目标值接近数组中的最高元素，则它很可能位于数组末尾附近。
引用自：https ://en.wikipedia.org/wiki/Binary_search_algorithm
主页：https ://en.wikipedia.org/wiki/Interpolation_search
在均匀分布的假设下，它可以接近O(log log N)
由于如今 CPU 与内存访问相比是如此之快（用于 RAM 的程序就像您曾经为磁盘所做的那样），因此与每次数据获取相比，索引/比较计算可能很便宜。一旦搜索范围足够窄（利用内存/缓存局部性），也可以通过线性搜索获得更多性能。
于 2020-11-02T12:23:36.007 回答
1
虽然在一般情况下你不能比 O(log N) 做得更好，但你至少可以优化它，从而显着降低 O(log N) 前面的比例常数。
如果您必须对同一个数组执行多次搜索，可以使用 SIMD 扩展对其进行矢量化，从而进一步降低计算成本。
特别是，如果您正在处理满足某些属性的浮点数数组，那么有办法构造一个特殊索引，然后允许在 O(1) 中搜索数组。
以上所有方面都在测试结果中进行了讨论： Cannizzo, 2015, Fast and Vectorizable Alternative to Binary Search in O(1) 适用于广泛的浮点数排序数组 论文随附github上的源代码。
于 2017-05-20T02:24:38.817 回答
0
如果您有大量的数字要查找，并且出于某种侥幸，它们也已排序，您可以在 O(n + m) 中进行，其中 m 是要查找的数字的数量。基本上只是典型的合并算法，稍作修改以记录每个检查的数字将在之前插入哪个值，如果它要插入到数组中。
你总是可以权衡空间......和其他操作的时间。假设您的所有元素都是恒定大小的 p 位，您可以创建一个庞大的数组，对于您可以查找的每个可能值，该数组存储当前存储的下一个较大值的索引。该数组需要为 2^p*lg(n) 位，其中 n 是存储的数值。每次插入或删除都是 O(2^p)，但通常在 2^p/n 左右，因为您必须更新所有这些索引。
但是您的查找现在是 O(1)！
好的，好的，这不是很实用。但是以类似的方式将输入分成块可能会减少日志前面的常数。可能。
于 2010-10-30T13:33:54.383 回答
0
在二进制搜索中，您将列表分成两个“子列表”，并且您只搜索可能包含该值的子列表。根据阵列的大小，如果将阵列分成两个以上的接头，您可能会看到加速。
您可以通过保留首先搜索的索引来确定必须搜索的数组区域。就像在一个大城市的电话簿里，你可以从外面看到，你必须从哪里开始搜索。（我无法用文字表达我的想法，而且我还没有找到可以更好地解释它的英文链接）。
于 2010-10-30T04:57:02.723 回答
0
正如有人提到的，您可以尝试插值搜索。但通常插值搜索非常简单/愚蠢，采用简单的线性方法（如果数组 A 中的值分布均匀，则效果很好，但如果分布以某种方式严重偏斜，则效果很差）。
这个想法是将数组 A 视为一个数学函数（因为它是排序的，一对一的函数），然后对其进行近似。假设您有一个包含 100 个值的数组 A，其中 A[x]=2*x。现在你想将 9 插入到你的数组中，并替换最接近它的任何值。
使用二分搜索，您将找到 A[50]=100，然后是 A[25]=50，然后是 A[12]=24，然后是 A[6]=12，然后是 A[3]=6，然后A[4]=8，最后 A[5]=10。设置 A[5]=9，我们就完成了。
通过线性插值搜索，取第一个和最后一个值 A[0]=0 和 A[99]=198，可以计算出两个 f(x)=2*x 之间的线性函数。倒数将是 g(x)=x/2。所以代入9，g[9]=4.5，A[5]=10 大于9，检查之前的值A[4]=8，就大功告成了。这只是 2 次查找和比较，而二进制搜索则需要 7 次。对于一个非常大的数组，您可以看到这可以显着减少您的查找和比较。
现在，在现实世界中，您通常不会有一个像这样具有简单线性范围值的数组。它们将偏向一侧或另一侧，您将不得不递归地进行多次插值搜索，或者在第一次或第二次插值之后切换到线性或二进制搜索，或类似的东西。
如果您知道数组 A 中的值严重偏斜（例如，您有一个包含 100 个值的数组 A，其中前 90 个值是 1，后 10 个值是 1 到 10 的范围），那么您知道插值可能是走错路了。二进制搜索将使您在大约相同的时间内或更快地到达那里。
您可以变得更花哨并尝试构建一些其他近似于反函数的数组 B，然后对其进行研究，或者甚至进行一些统计分析以创建一些近似于反函数的数学函数，但这超出了此答案的范围。
于 2021-10-13T19:40:00.557 回答