ura*_*ray 27 c++ arrays algorithm search binary-search
是否存在比二进制搜索更快的算法,用于搜索数组的排序值？
在我的情况下,我有一个A数组中的排序值(可能是任何类型值),n如果我看的值在范围内,我需要返回A[n] and A[n+1]
jon*_*rry 38
如果值是整数,则可以比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
一种可能性就是将其视为找到函数的根源.基本上,找到:
a[i] <= i <= a[i + 1]
相当于:
a[i] - i <= 0 <= a[i + 1] - i
然后你可以试试像牛顿的方法等等.这些类型的算法在工作时经常比二进制搜索收敛得快,但我不知道保证收敛所有输入的算法.
http://en.wikipedia.org/wiki/Root-finding_algorithm
是和否。是的，平均而言，有些搜索比二分搜索更快。但我相信它们仍然是 O(lg N)，只是常数较低。
您希望最大限度地减少查找元素所需的时间。通常希望使用较少的步骤，而解决此问题的一种方法是最大化将在每个步骤中消除的元素的预期数量。使用二分法，总是正好消除一半的元素。如果您对元素的分布有所了解，您可以做得比这更好。但是，选择分区元素的算法通常比选择中点更复杂，这种额外的复杂性可能会压倒您希望通过使用更少的步骤获得的任何时间节省。
确实，在这样的问题中，与搜索算法相比，攻击缓存局部性等二阶效应更好。例如，在进行重复二分查找时，相同的几个元素（第一、第二和第三四分位数）被非常频繁地使用，因此将它们放在单个缓存行中可能比随机访问列表要好得多。
将每个级别划分为 4 或 8 个相等的部分（而不是 2 个）并通过这些进行线性搜索也可能比二分搜索更快，因为线性搜索不需要计算分区并且还具有较少的数据依赖性，可以导致缓存停顿。
但所有这些仍然是 O(lg N)。
如果列表中的值均匀分布,那么您可以尝试加权拆分而不是二进制拆分,例如,如果所需的值是从当前下限到当前值的三分之一,那么您可以尝试使用也是三分之一.这可能会在列表中受到严重影响,但是这些值会被聚集起来.
小智 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 ，但我不知道。