均匀搜索数组的常数搜索算法？

Question

我一直在寻找一种好的搜索算法，然后我遇到了插值搜索算法，该算法的时间复杂度为O（log（log（n（n）））），只能应用于均匀分布的数组。但是，我发现可以创建一个要求相同条件但时间复杂度为O（1）的搜索算法。这是我想出的：（C ++代码）

int search(double Find, double* Array, const int Size) {
    if (Array[0] == Array[1] && Find == Array[0]) { return 0; }
    if (Array[0] == Array[1] && Find != Array[0]) { return -1; }
    const double Index = (Find - Array[0]) / (Array[Size - 1] - Array[0]) * (Size - 1.0);
    if (Index < 0 || Index >= Size || Array[(int)(Index + 0.5)] != Find) { return -1; }
    return Index + 0.5; 
}

在此函数中，我们传递要查找的数字，数组指针和数组的大小。此函数返回要找到的数字所在的索引；如果找不到，则返回-1。

说明：好吧，在没有任何图片的情况下进行解释将非常困难，我将尽我所能...

由于数组是均匀分布的，我们可以将它的所有值表示在图上，其中索引号（比方说x）为横坐标，而数组在此索引处的值（比方说Arr [x]）为纵坐标。好了，我们可以看到图上表示的所有点都属于方程的函数：

Array [x] = tan（A）* x + Arr [0]->以A为函数与图形的x轴之间的夹角。

所以现在，我们可以将等式转换为：

x =（Arr [x]-Arr [0]）/ tan（A）

就是这样，x是相对于Arr [x]（要搜索的给定值）要找到的索引。我们可以将公式更改为x =（Arr [x]-Array [0]）/（Array [Size-1]-Array [0]）*（Size-1.0）因为我们知道tan（A）=（Array [Size-1]-Array [0]）/（Size-1.0）。

问题（最后...）

我想这个公式已经在某些程序中使用了，很容易找到...所以我的问题是，为什么我们要使用插值搜索代替它？我不明白吗？

感谢您的耐心和帮助。

Answer 1

[当谈到均匀分布时，这并不意味着一旦知道排序数组中的第一个和最后一个值，便也知道其他值。这就是您的算法所假设的。均匀分布与生成数组时涉及的概率有关，但是在按照这种均匀分布原理生成的实际数组中，您仍然可以获得看起来不那么均匀分布的数组。这是一个概率问题。平均而言，这些值将平均分配，但这不能保证。

其次，您的算法实际上是一种插值算法，其区别在于它假定在第一次查找之后，它一定已经到达了该值应位于的位置。然而，在随机产生的数组（均匀分布）中，这是无法保证的，因此必须在较小的间隔上重复操作，直到该间隔接近一个索引为止。