搜索算法及其复杂性

Question

我在一次采访中被问到这个问题:假设一个无限个整数数组被排序。如何在此数组中搜索整数？时间的复杂性是什么？我猜到面试官所说的无限是什么意思，我们不知道'n‘的值，其中n是数组中最大数的指数。我给出了以下答案：

SEARCHINF(A,i,x){ // Assume we are searching for x
if (A(1) > x){
   return
}
if(A(i) == x){
   return i;
}
else{
    low = i;
    high = power(2,i);
    if (A(i)>x){
       BINARY-SEARCH(A,low,high);
    }
    else{
        SEARCHINF(A,high,x);
    }
}// end else
}// end SEARCHINF method

在最坏的情况下，这将在(log x+ 1)时间内找到界(低和高)，此时排序的数字从1开始，随后出现后续数。然后，二进制搜索需要：

O( log {2^(ceil(log x)) - 2^(floor(log x))} )

这是正确的吗？如果是正确的话，这能被优化吗？

Answer 1

排序数组确实给出了它:二进制排序。

最坏情况: O(lg(n))。找不到更快、更可靠的方法了。

当然，你可以告诉他，在无限数组中找到一个元素要花费很长时间。