比二进制搜索有序列表快

如果值是整数,则可以比O(log n)做得更好,在这种情况下,就n而言,可以实现的最佳最坏运行时间是O(sqrt(logn))。否则,除非输入序列中存在模式,否则无法击败O(log n)。在整数的情况下,有两种方法用来击败O(log n)。

首先,可以使用y-fast树,它的工作原理是将所有前缀存储在哈希表中,并且至少要为这些前缀存储一个整数。这使您能够执行二进制搜索以查找最长匹配前缀的长度。这使您能够在时间O(log w)中查找要搜索的元素的后续元素,其中w是单词中的位数。虽然有一些细节要做的工作,使这个工作,只使用线性空间,但他们并不太坏(见下面的链接)。

其次,您可以使用fusion树,它使用位技巧使您能够在恒定数量的指令中执行w^O(1)比较,从而产生O(log n/logw)的运行时间。

当log w=sqrt(log n)时,这两种数据结构之间的最佳折衷出现,运行时间为O(sqrt(logn))。

有关上述内容的详细信息,请参见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)。

下面的算法呢? 它被称为指数搜索,是二进制搜索的变体之一。 http://en.m.wikipedia.org/wiki/Exponential_search

在大小为n的排序数组A中搜索元素k。 查找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的索引(两个stpe都在logidx中)。在最坏的情况下,如果k是A的最大元素之一或大于A的任何元素,则algo在O(log idx)中。乘法常数大于二进制搜索,但对于非常大的数组和查找接近数组开头的数据时,algo会运行得更快。

我想知道这个算法比二进制搜索更可取的最小大小n,但我不知道。

你可以把它们放在一个散列表中,然后搜索将是O(1)。但这将占用大量内存,如果继续添加项,则可能需要重新对哈希表进行绑定。再扣是O(n),但它将被摊销到O(1)。它本质上取决于您是否能负担得起该空间和潜在的缓存未命中。

首先, 测量

你真的需要优化搜索吗?

如果是,那么第二,首先考虑算法的复杂性。E、 你能用一棵树吗 std::map ,例如)而不是数组?如果是这样,则取决于插入/删除与搜索的相对频率,但前提是手头有一个排序数组,这表明与数据集更改相比,搜索是频繁的,因此对插入/删除做一些额外的工作是有意义的,使每次搜索都快得多——即对数时间。

如果您发现搜索时间确实是一个需要解决的瓶颈,而且不,不可能更改数据表示,而且列表很短,那么线性搜索通常会更快,因为它每次比较所做的工作更少。

否则,如果列表较长,并且不知道或假设值的特定分布,并且这些值不能被视为数值,并且内存消耗应该是恒定的(例如,排除构造哈希表的可能性),然后二进制搜索每次比较产生1位信息,可能是第一次搜索所能做的最好的。

干杯。

虽然在一般情况下你不能做得比O(log N)更好,但是你至少可以优化它,从而显著地减少O(logn)前面的比例常数。

如果必须在同一个数组上执行多个搜索,则可以使用SIMD扩展对其进行矢量化,从而进一步降低计算成本。

以上所有方面都将在中与测试结果进行讨论: Cannizzo, 2015, Fast and Vectorizable Alternative to Binary Search in O(1) Applicable to a Wide Domain of Sorted Arrays of Floating Point Numbers 这篇论文的源代码 github

在二进制搜索中,您将列表分成两个“子列表”,并且只搜索可能包含该值的子列表。根据阵列的大小,如果将阵列拆分为两个以上的拼接,则可以看到加速。

如果你有大量的数字要找,并且侥幸它们也被排序,你可以在O(n+m)中找到,其中m是要找的数字的数目。基本上只是典型的合并算法,如果要将每个选中的数字插入到数组中,只需稍加修改就可以记录下它之前将插入的值。

你总是可以交换空间。。。以及其他行动的时间。假设所有元素都是固定大小的p位,那么您可以创建一个庞大的数组,该数组存储当前存储的下一个较大值的索引(对于您可以查找的每个可能值)。这个数组需要2^p*lg(n)位,其中n是存储的数值。每次插入或删除都是O(2^p),但通常是2^p/n左右,因为您必须更新所有这些索引。

但是你的查找结果现在是O(1)!

好吧,好吧,这不太实际。但是以类似的方式将输入分成块可能会减少日志前面的常量。可能吧。