搜索算法及其复杂性

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

在最坏的情况下,当排序的数字从1开始,随后的数字结束时,这将在(log x + 1)时间内找到界限(低和高).然后二进制搜索需要:

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

它是否正确？如果正确,可以优化吗？

Answer 1

使用将索引加倍的方法，直到通过它，然后对您刚刚跳过的区域进行二分搜索（看起来您的伪代码正在尝试执行的操作），花费的时间应该是 O(log ₂ n)，其中 n 是索引您正在搜索的项目的名称。

它将需要您 (log ₂ n) 尝试找到正确的区域，然后 ((log ₂x n) - 1) 尝试在该区域内查找（因为您已经从 0..n/2 开始搜索，所以您只需要搜索 n/2..n)。因此，O(log ₂ n + log ₂ n - 1) = O(log ₂ n)。

但是，如果“无限数组”不包含x或任何大于 的值x，您将永远不会知道，因为您将永远搜索。