高效搜索排序数值

Question

我有一个包含下列属性值的int[]数组：

• 它们是已排序的
• 它们是唯一的(没有重复)
• 它们在一个已知的范围内[0..MAX)
• MAX通常比数组的长度大得多(比如10-100倍)
• 有时这些数字在该范围内均匀分布，但有时也有相当长的连续数字序列。我的估计是，这两种情况之间大约是50/50的比例。

鉴于此列表，我希望能够高效地查找数组中特定值的索引(或者如果该值不存在，则查找下一个更高的值)。

我已经实现了一种使用区间二分的直接二进制搜索算法，效果还不错，但我怀疑数据的性质/分布可以利用起来更快地收敛到解。

我对优化平均情况的搜索时间感兴趣，但最坏情况不能比O(log n)更差，因为有时数组非常大。

问题：是否可以在平均情况下做得比简单的二进制搜索好得多？

编辑(为了澄清其他问题/评论):

• O(log n)中的常数确实很重要。事实上，假设除O(log n)外没有更好的算法复杂度，那么常数可能是唯一重要的事情.....
• 经常只需要搜索一次，因此虽然预处理是可能的，但可能不值得。

- mikera

---

你要搜索多少次？将它们放入Map中将会得到O(1)的搜索时间，但设置需要O(n)的时间。另外，你不需要实现二分查找，Arrays.binarySearch已经可以满足你的要求。 - Boris the Spider

如果确实存在大量连续的数字块（没有重复项），您可以修改二分搜索算法以识别何时到达一个（是否为 x[end] - x[start] == end - start？），然后直接跳转到解决方案。请注意，此方法依赖于非常长的连续序列，否则您将无法消除许多递归阶段。 - Oliver Charlesworth

你尝试过使用插值搜索吗？http://zh.wikipedia.org/wiki/%E6%8F%92%E5%80%BC%E6%90%9C%E7%B4%A2 - NPE

我认为O(log n)中的常数对你也很重要，对吗？为什么不做一个类似于二分查找的算法，但每次将数组分成3或4个子数组呢？然后进行一些实验。 - peter.petrov

@peter.petrov：如果你的插值方法不够智能，那么它可能会很糟糕。这真的取决于数据。如果分布相对均匀，智能插值搜索将胜过直接二进制搜索。如果数据分布不相对均匀，则二进制搜索可能是更好的选择。OP说它可能是50/50（均匀分布与连续值的长时间间隔）。我认为需要针对几个代表性数据集运行测试才能确定哪种方法更好。 - T.J. Crowder

Answer 1

这是评论，应该是一个答案。这是一个共同努力，所以我将其制作为CW答案：

您可以考虑使用插值搜索。在最坏情况下，它们可能比O(log n)更糟，因此如果这是硬性要求，则不适用。但是，如果您的插值很好，并且取决于数据分布，则插值搜索可以击败直接二进制搜索。

为了知道结果，您需要使用合理聪明的插值算法实现插值搜索，然后通过两种方法运行几个代表性数据集，以查看哪种方法更适合使用：插值或二进制搜索。我认为这将是其中之一，但我不熟悉真正尖端的搜索算法。

- T.J. Crowder

Answer 2

让我们将区间命名为x，搜索的数字为z。

由于您希望值均匀分布，因此可以使用插值搜索。这类似于二分搜索，但在start + ((z - x[start]) * (end - start)) / (x[end] - x[start])处分割索引范围。

要获得O(log n)的运行时间，必须将插值搜索与二分搜索相结合(交替执行二分搜索和插值搜索的步骤)：

public int search(int[] values, int z) {
    int start = 0;
    int end = values.length-1;

    if (values[0] == z)
         return 0;
    else if (values[end] == z) {
        return end;
    }

    boolean interpolation = true;

    while (start < end) {
        int mid;
        if (interpolation) {
            mid = start + ((z - values[start]) * (end - start)) / (values[end] - values[start]);
        } else {
            mid = (end-start) / 2;
        }
        int v = values[mid];
        if (v == z)
            return mid;
        else if (v > z)
            end = mid;
        else
            start = mid;
        interpolation = !interpolation;
    }
    return -1;
}

由于 while 循环的每次第二次迭代都会进行二分搜索，因此它使用的迭代次数最多是二分搜索所需迭代次数的两倍（O(log n)）。由于每个第二步都是插值搜索的一步，如果输入具有所需的属性，则算法应快速缩小区间大小。

- fabian

Answer 3

如果 int[]

• 已排序
• 具有唯一值
• 您知道范围（提前）

那么，为什么不保存其索引处的值，而不是搜索。

假设数字为243，则将该值保存在int [243] = 243中。

这样搜索将更容易和更快。 唯一剩下的事情就是找出下一个更高的值。

- Tabrej Khan

---

原文：The OP said "MAX is typically quite a lot larger than the length of the array (say 10-100x)" so this would be very memory-expensive.翻译：原帖作者说：“MAX通常比数组长度要大很多（比如10-100倍）”，因此这会占用很多内存。 - T.J. Crowder

Answer 4

我有一个解决方案。
您说数组可以是
1) 数字均匀分布在范围内
2) 有相当长的连续数字序列。

因此，首先我们开始进行简单的测试，以确保它是类型1还是类型2。
要测试类型1，
长度 = array.length;
范围 = array[length-1] - array[0];
现在考虑数组中的值
  {length(1/5),length(2/5),length(3/5),length(4/5)},
如果数组分配是类型1，则我们近似知道array[i]必须是什么值，所以我们检查上述4个位置是否接近已知值，如果是等分布。
如果它们很接近，则为等分布，因此我们可以轻松找到数组中的任何元素。 如果我们无法根据上述方法找到元素，则认为它是类型2。

如果上述测试失败，则为类型2，这意味着在数组中存在少量连续数字序列的位置。

所以，我们可以用二分查找的方式来解决它。以下是解释：
*首先，在数组的中间位置进行搜索（例如在长度/2处，索引为i）

left=0，right=length;
BEGIN:
i=(left+right)/2;

情况a.1：我们要查找的数字大于数组[i]
left=i;
*现在我们检查该位置是否存在长连续序列，即array[i]、array[i+1]、array[i+2]是连续的整数。

情况a.1.1：（如果它们是连续的），
由于它们是连续的，并且序列可能很长，我们直接根据我们的搜索整数值在特定的索引处进行搜索。
例如，如果我们要搜索的整数是10，序列是5、6、7、8、9、10、11、15、100、103，而array[i]=5，则我们直接在array[i+10-5]处进行搜索，
如果我们找到了我们要搜索的整数，则返回它，否则只能从情况a.2继续[因为它显然会小于它]，将right设置为
right=(array[i+10-5])

情况a.1.2，如果它们不连续
从BEGIN继续;

情况a.2：我们搜索的数字小于数组[i]，
*情况a.2与a.1完全相似
*同样检查是否有后退序列，即array[i-2]，array[i-1]，array[i]按顺序排列，
如果它们按顺序排列，就像在情况a.1.1中一样向后搜索到精确值
如果它们不连续，请重复类似于情况a.1.2。

情况a.3，这是我们搜索的整数，
然后返回它。

希望这有所帮助

- santhu