比有序列表的二分搜索快 [英] Faster than binary search for ordered list

问题描述

是否有比二分查找更快的算法，用于在数组的排序值中进行搜索?

is there an algorithm that is faster than binary search, for searching in sorted values of array?

在我的例子中，我在 A 数组中有一个排序的值(可以是任何类型的值)，如果我正在寻找的值是，我需要返回 nA[n] 和 A[n+1]

in my case, I have a sorted values (could be any type values) in an A array, I need to return n if the value I was looking is in range of A[n] and A[n+1]

推荐答案

如果值是整数，您可以做得比 O(log n) 更好，在这种情况下，您可以达到的最佳最坏情况运行时间，就n，是 O(sqrt(log n)).否则，除非输入序列中存在模式，否则无法击败 O(log n).在整数的情况下，有两种方法可以击败 O(log n).

You can do better than O(log n) if the values are integers, in which case the best worst-case running time you can achieve, in terms of n, is O(sqrt(log n)). Otherwise, there is no way to beat O(log n) unless there are patterns in the input sequence. There are two approaches used to beat O(log n) in the case of integers.

首先，您可以使用 y-fast 树，它的工作方式是将所有前缀存储在哈希表中，您至少要为其存储一个具有该前缀的整数.这使您能够执行二进制搜索以查找最长匹配前缀的长度.这使您能够在 O(log w) 时间内找到您正在搜索的元素的后继元素，其中 w 是一个字中的位数.虽然有一些细节可以使这项工作正常工作并且仅使用线性空间，但它们还不错(请参阅下面的链接).

First, you can use y-fast trees which work by storing in a hash table all prefixes for which you are storing at least one integer with that prefix. This enables you to perform a binary search to find the length of the longest matching prefix. This enables you to find the successor of an element for which you are searching in time O(log w) where w is the number of bits in a word. There are some details to work though to make this work and use only linear space, but they aren't too bad (see the link below).

其次，您可以使用融合树，它使用一些技巧使您能够在恒定数量的指令中执行 w^O(1) 比较，从而产生 O(log n/log w) 的运行时间.

Second, you can use fusion trees, which use bit tricks to enable you to perform w^O(1) comparisons in just a constant number of instructions, yielding a running time of O(log n / log w).

当log w = sqrt(log n)，运行时间为O(sqrt(log n))时，这两种数据结构之间的最佳权衡发生.

The optimum tradeoff between these two data structures occurs when log w = sqrt(log n), giving a running time of O(sqrt(log n)).

有关上述内容的详细信息，请参阅 Erik Demaine 课程的第 12 和 13 课:http://courses.csail.mit.edu/6.851/spring07/lec.html

For details on the above, see lectures 12 and 13 of Erik Demaine's course: http://courses.csail.mit.edu/6.851/spring07/lec.html

这篇关于比有序列表的二分搜索快的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！