是否有一种比二进制搜索更快的算法，用于搜索数组的排序值？
在我的情况下，我在 A 数组中有一个排序值（可以是任何类型值），如果我看的值在 A[n] and A[n+1] 范围内，我需要返回 n
A
A[n] and A[n+1]
n
如果值是整数，则可以比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
如果列表中的值均匀分布，那么您可以尝试加权拆分而不是二进制拆分，例如如果所需的值是从当前下限到当前值的三分之一，那么您可以尝试也是三分之一的元素 . 尽管如此，这可能会严重影响 Value .
是的，不是 . 是的，平均而言，搜索比二分搜索更快 . 但我相信它们仍然是O（lg N），只是具有较低的常数 .
您希望最大限度地缩短查找元素所需的时间 . 通常希望使用较少的步骤，并且一种方法是最大化在每个步骤将消除的预期元素数量 . 通过二分法，总是可以消除一半的元素 . 如果你对元素的分布有所了解，你可以做得更好 . 但是，选择分区元素的算法通常比选择中点更复杂，而这种额外的复杂性可能会超过您期望从使用更少步骤获得的任何时间节省 .
实际上，在这样的问题中，攻击二阶效应（如缓存局部性）比搜索算法更好 . 例如，在进行重复二进制搜索时，非常频繁地使用相同的几个元素（第一，第二和第三四分位数），因此将它们放在单个缓存行中可能远远优于对列表的随机访问 .
将每个级别划分为4个或8个相等的部分（而不是2个）并对其进行线性搜索也可能比二分搜索更快，因为线性搜索不需要计算分区，也可以减少数据依赖性导致缓存停顿 .
但所有这些仍然是O（lg N） .
以下算法怎么样？它被称为指数搜索，是二元搜索的变体之一 . http://en.m.wikipedia.org/wiki/Exponential_search
在大小为n的有序数组A中搜索元素k . 查找A [2 ^ i]为i = 0,1,2，...直到你超越了在A中的k位置，然后对数组左边（小于）的部分进行二分搜索 .
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这个算法变得比二分搜索更可取，但我不知道 .
您始终可以将它们放在哈希表中，然后搜索将是O（1） . 它会占用大量内存，如果你不断添加项目，哈希表可能需要重新分配 . 重新分组是O（n）但它将分摊到O（1） . 这主要取决于你是否能负担得起这个空间和潜在的缓存未命中 .
首先，在做之前 measure 优化 .
你真的需要优化搜索吗？
如果是这样，那么其次，首先考虑算法复杂性 . 例如 . 你可以使用树（比如 std::map ，而不是数组）吗？如果是这样，那么它取决于插入/删除与搜索的相对频率，但是手头有一个排序数组的前提表明，与数据集更改相比，搜索频繁，因此为了做一些额外的工作是有意义的 . 插入/删除，使每次搜索更快 - 即对数时间 .
std::map
如果您发现搜索时间确实是需要解决的瓶颈，并且没有，数据表示不可能更改，并且列表很短，那么线性搜索通常会更快，因为每次比较的工作量更少 .
否则，如果列表较长，并且没有特定的值分布已知或假设，并且值不能被视为数值，并且内存消耗应该是常量（排除构造哈希表，比如说），那么二进制搜索每次比较产生1位信息，可能是您第一次搜索时可以做的最好的信息 .
干杯和hth .
在二进制搜索中，您将列表拆分为两个“子列表”，并且只搜索可能包含该值的子列表 . 根据数组的大小，如果将数组拆分为两个以上的拼接，则可以看到加速 .
您可以通过保留索引来确定首先搜索的阵列的哪个区域 . 就像在一个大城市的电话簿中，你可以从外面看到，你必须开始搜索 . （我无法在文本中表达我的想法，但我找不到更好地解释它的英文链接） .
如果您有大量的数字可供查找，并且通过一些侥幸它们也被排序，您可以在O（n m）中进行，其中m是要查找的数字的数量 . 基本上只是你的典型合并算法，稍微修改一下，记录每个检查过的数字之前插入的值，如果它要插入到数组中 .
你可以随时换取空间......以及其他操作的时间 . 假设所有元素都是常量p位，你可以创建一个庞大的数组，为你可以查找的每个可能的值存储当前存储的下一个更大值的索引 . 该数组需要是2 ^ p * lg（n）位，其中n是存储的数值 . 每次插入或删除都是O（2 ^ p），但通常约为2 ^ p / n，因为您必须更新所有这些索引 .
但是你的查找现在是O（1）！
好的，好的，这不太实际 . 但是以类似的方式将输入划分为块可能会减少日志前面的常量 . 有可能 .
虽然在一般情况下你不能做得比O（log N）好，但你至少可以优化它，从而显着减少O（log N）前面的比例常数 .
如果必须在同一阵列上执行多次搜索，可以使用SIMD扩展对这些进行矢量化，从而进一步降低计算成本 .
特别是，如果要处理满足某些属性的浮点数数组，那么有多种方法可以构造一个特殊的索引，然后允许在O（1）中搜索数组 .
所有上述方面都与测试结果进行了讨论：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的源代码 .
10 回答
如果值是整数，则可以比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
一种可能性就是将其视为找到函数的根源 . 基本上，找到：
相当于：
然后你可以尝试像牛顿的方法等等 . 这些算法在工作时经常比二进制搜索收敛得更快，但我不知道哪一种算法可以保证为所有输入收敛 .
http://en.wikipedia.org/wiki/Root-finding_algorithm
如果列表中的值均匀分布，那么您可以尝试加权拆分而不是二进制拆分，例如如果所需的值是从当前下限到当前值的三分之一，那么您可以尝试也是三分之一的元素 . 尽管如此，这可能会严重影响 Value .
是的，不是 . 是的，平均而言，搜索比二分搜索更快 . 但我相信它们仍然是O（lg N），只是具有较低的常数 .
您希望最大限度地缩短查找元素所需的时间 . 通常希望使用较少的步骤，并且一种方法是最大化在每个步骤将消除的预期元素数量 . 通过二分法，总是可以消除一半的元素 . 如果你对元素的分布有所了解，你可以做得更好 . 但是，选择分区元素的算法通常比选择中点更复杂，而这种额外的复杂性可能会超过您期望从使用更少步骤获得的任何时间节省 .
实际上，在这样的问题中，攻击二阶效应（如缓存局部性）比搜索算法更好 . 例如，在进行重复二进制搜索时，非常频繁地使用相同的几个元素（第一，第二和第三四分位数），因此将它们放在单个缓存行中可能远远优于对列表的随机访问 .
将每个级别划分为4个或8个相等的部分（而不是2个）并对其进行线性搜索也可能比二分搜索更快，因为线性搜索不需要计算分区，也可以减少数据依赖性导致缓存停顿 .
但所有这些仍然是O（lg N） .
以下算法怎么样？它被称为指数搜索，是二元搜索的变体之一 . http://en.m.wikipedia.org/wiki/Exponential_search
在大小为n的有序数组A中搜索元素k . 查找A [2 ^ i]为i = 0,1,2，...直到你超越了在A中的k位置，然后对数组左边（小于）的部分进行二分搜索 .
该算法将在O（log idx）上运行，其中idx是A中的k的索引 . （两个stpes都在log idx中） . 在最坏的情况下，算法在O（log idx）中，如果k是A的最大元素之中或者比A的任何元素都大 . 乘法常数大于二进制搜索但算法运行速度更快，非常大数组以及查找朝向数组开头的数据 .
我想知道最小尺寸n这个算法变得比二分搜索更可取，但我不知道 .
您始终可以将它们放在哈希表中，然后搜索将是O（1） . 它会占用大量内存，如果你不断添加项目，哈希表可能需要重新分配 . 重新分组是O（n）但它将分摊到O（1） . 这主要取决于你是否能负担得起这个空间和潜在的缓存未命中 .
首先，在做之前 measure 优化 .
你真的需要优化搜索吗？
如果是这样，那么其次，首先考虑算法复杂性 . 例如 . 你可以使用树（比如
std::map，而不是数组）吗？如果是这样，那么它取决于插入/删除与搜索的相对频率，但是手头有一个排序数组的前提表明，与数据集更改相比，搜索频繁，因此为了做一些额外的工作是有意义的 . 插入/删除，使每次搜索更快 - 即对数时间 .如果您发现搜索时间确实是需要解决的瓶颈，并且没有，数据表示不可能更改，并且列表很短，那么线性搜索通常会更快，因为每次比较的工作量更少 .
否则，如果列表较长，并且没有特定的值分布已知或假设，并且值不能被视为数值，并且内存消耗应该是常量（排除构造哈希表，比如说），那么二进制搜索每次比较产生1位信息，可能是您第一次搜索时可以做的最好的信息 .
干杯和hth .
在二进制搜索中，您将列表拆分为两个“子列表”，并且只搜索可能包含该值的子列表 . 根据数组的大小，如果将数组拆分为两个以上的拼接，则可以看到加速 .
您可以通过保留索引来确定首先搜索的阵列的哪个区域 . 就像在一个大城市的电话簿中，你可以从外面看到，你必须开始搜索 . （我无法在文本中表达我的想法，但我找不到更好地解释它的英文链接） .
如果您有大量的数字可供查找，并且通过一些侥幸它们也被排序，您可以在O（n m）中进行，其中m是要查找的数字的数量 . 基本上只是你的典型合并算法，稍微修改一下，记录每个检查过的数字之前插入的值，如果它要插入到数组中 .
你可以随时换取空间......以及其他操作的时间 . 假设所有元素都是常量p位，你可以创建一个庞大的数组，为你可以查找的每个可能的值存储当前存储的下一个更大值的索引 . 该数组需要是2 ^ p * lg（n）位，其中n是存储的数值 . 每次插入或删除都是O（2 ^ p），但通常约为2 ^ p / n，因为您必须更新所有这些索引 .
但是你的查找现在是O（1）！
好的，好的，这不太实际 . 但是以类似的方式将输入划分为块可能会减少日志前面的常量 . 有可能 .
虽然在一般情况下你不能做得比O（log N）好，但你至少可以优化它，从而显着减少O（log N）前面的比例常数 .
如果必须在同一阵列上执行多次搜索，可以使用SIMD扩展对这些进行矢量化，从而进一步降低计算成本 .
特别是，如果要处理满足某些属性的浮点数数组，那么有多种方法可以构造一个特殊的索引，然后允许在O（1）中搜索数组 .
所有上述方面都与测试结果进行了讨论：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的源代码 .