为了搜索一个非常大的数组，我正在考虑一个复杂度小于 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- 我有一个接近均匀分布的数组。
我想问一下它真的比二分查找好吗？？在什么情况下它会失败？什么是最好的，平均的和最坏的情况复杂度？？
最佳答案
您正在使用启发式方法来尝试加速排序。启发式就像猜测。不能保证它是正确的 - 但如果启发式是好的，则可以在一般情况下加速算法。
启发式算法通常不会改善算法在最坏情况下的运行时间。也就是说 - 启发式的某些输入可能是错误的。
我可以看到您正在做的事情的直观吸引力 - 您正在“搜索”更接近您认为目标的位置。
但是你的做法有两个问题:
- 将二分搜索中的“拆分”移近目标并不会加快搜索速度。在二进制搜索中，每次将搜索空间分成两半。当你将分割点移近目标时，你还没有找到目标，你的目标很可能在两个不相等空间中较大的一个。
例如，假设您有以下数组。 y 是您的目标，x 是所有其他值:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx
在二分搜索中，您会在前两个决定中将空间分成两半，然后再分成两半:
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx
^ ^
经过两次决定后，您的 32 值数组缩小到 8 个值的搜索空间。但是假设根据您的启发式，在第二个选择之后您将拆分放在 y 之后？
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxYxx
^ ^
在您做出第二个决定后，您只稍微缩小了搜索空间。通过添加此启发式算法，您已将最坏情况下的运行时间减少到 N - 因为可以构造输入，让您的启发式算法每次都做出最坏的猜测。
- 另一个问题是，加速搜索的启发式方法只有在您对所搜索的内容有所了解时才有用。以字典搜索为例。你知道 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。
关于algorithm - 在排序数组中搜索比二进制搜索复杂度低，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26585931/