比二进制搜索排序列表更快 [英] 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 数组，我需要回到 N ，如果我一直在寻找的值在范围 A [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（开方（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型快树，通过存储在哈希表中的所有prefixes要为其存储与preFIX至少有一个整数的工作。这使您能够执行二进制搜索找到的最长匹配preFIX的长度。这使您能够找到您正在搜索的时间为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），在短短一个恒定的指令数，产生邻运行时间比较（日志N /日志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).

在日志W =开方（log n）的，给人Ø运行时间（的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)).

有关上述详细信息，请参阅讲座12和13埃里克Demaine的当然是：<一href="http://courses.csail.mit.edu/6.851/spring07/lec.html">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屋！