algorithm - 在排序数组中搜索比二进制搜索复杂度低

Question

为了搜索一个非常大的数组，我正在考虑一个复杂度小于 log n 的算法，这意味着不是阶数小于 log n，而是绝对小于 log n。所以我所做的是而不是去中间向前移动 1 步并检查如果数字均匀分布我们必须进一步移动多少，移动到该位置，如果这是解决方案则打破它否则计算我们必须进一步移动多少，迭代执行直到找到解决方案这是一个有效的 Java 代码:-

 public class Search {
        public static void main(String[] args) {
            int a[]={12,15,16,17,19,20,26,27};
            int required=27;
            int pointer=0;
            int n=1;
            int diff;
            int count=0;
            int length=a.length;
            while(a[pointer]!=required){
                count++;
                if ((pointer+n)>(length-1))
                    n=length-1-pointer;
                if(n==0)
                    n=-1;
                diff=a[pointer+n]-a[pointer];
                pointer=pointer+n;
                n=(required-a[pointer])*n/diff;


            }
            System.out.println(pointer);
            System.out.println(count);
        }

    }

P.S- 我有一个接近均匀分布的数组。

我想问一下它真的比二分查找好吗？？在什么情况下它会失败？什么是最好的，平均的和最坏的情况复杂度？？

Answer 1

您正在使用启发式方法来尝试加速排序。启发式就像猜测。不能保证它是正确的 - 但如果启发式是好的，则可以在一般情况下加速算法。

启发式算法通常不会改善算法在最坏情况下的运行时间。也就是说 - 启发式的某些输入可能是错误的。

我可以看到您正在做的事情的直观吸引力 - 您正在“搜索”更接近您认为目标的位置。

但是你的做法有两个问题:

1. 将二分搜索中的“拆分”移近目标并不会加快搜索速度。在二进制搜索中，每次将搜索空间分成两半。当你将分割点移近目标时，你还没有找到目标，你的目标很可能在两个不相等空间中较大的一个。

例如，假设您有以下数组。 y 是您的目标，x 是所有其他值:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx

在二分搜索中，您会在前两个决定中将空间分成两半，然后再分成两半:

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx
                ^        ^

经过两次决定后，您的 32 值数组缩小到 8 个值的搜索空间。但是假设根据您的启发式，在第二个选择之后您将拆分放在 y 之后？

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx
                ^             ^

在您做出第二个决定后，您只稍微缩小了搜索空间。通过添加此启发式算法，您已将最坏情况下的运行时间减少到 N - 因为可以构造输入，让您的启发式算法每次都做出最坏的猜测。

1. 另一个问题是，加速搜索的启发式方法只有在您对所搜索的内容有所了解时才有用。以字典搜索为例。你知道 z 在字母表的末尾。所以当你得到一个以 z 开头的单词时，你就很清楚 z 单词在字典中的位置。您不必从字典的中间开始。

这是因为您对字典中单词的分布有所了解。但是，如果有人不能保证列表中的单词——那么你就不能保证字典搜索更快——例如，你可能会收到一个包含所有 z 个单词的列表。

在你的情况下，你的启发式并不是特别好。您猜测下一次拆分的位置基于当前拆分与先前值之间的距离。唯一一个好的猜测是列表中的元素是否均匀分布。如果它们间隔不均匀(几乎总是)，那么一些猜测总是会超过 split 和其他下冲。

在任何非均匀间隔数字的排序数组中，必然存在比平均间隔更紧密的间隔，以及比平均间隔更稀疏的间隔。您的启发式猜测当前拆分到数组末尾的数字的平均稀疏性。这两件事之间没有关系。

更新:

您的最佳案例时间:O(1) - 例如你马上就猜到了索引。

最坏情况:O(N) - 例如每一个选择都是最糟糕的。

您补充说您的阵列几乎均匀分布并且非常大。我猜测实际上什么是最快的:查找数组中的第一个数字和最后一个数字，以及数组的长度。对目标的偏移量进行有根据的猜测:

offset = floor((( target - first ) / ( last - first )) * length );

在目标周围选择一个合理的搜索空间:

window_start = floor( offset * ( 1 - alpha ));
window_end   = floor( offset * ( 1 + alpha ));

对该窗口定义的子数组进行二分查找。

将 alpha 设置为多少取决于您认为数组的规律性。例如。您可以将 设置为 0.05 以搜索大约占估计目标周围总搜索空间 10% 的窗口。

如果您可以对输入的均匀性做出一些保证，您也许可以优化调整 alpha。