搜索算法及其复杂度
我在一次采访中被问到这个问题：假设有一个已排序的无限整数数组。您将如何在该数组中搜索整数？时间复杂度是多少？ 我猜面试官所说的无限的意思是我们不知道“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))} )
这是正确的吗？如果正确的话可以优化吗？
I was asked this question in an interview: Assume an infinite array of integers which is sorted. How would you search for an integer in this array? What would be time complexity?
I guessed what the interviewer meant by infinite is that we dont know the value of 'n', where n is the index of the largest number in the array.
I gave the following answer:
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
This will find the bound(low and high) in (log x + 1) time in the worst case, when the sorted numbers start from 1 and subsequent numbers are consequent.
Then the binary search requires:
O( log {2^(ceil(log x)) - 2^(floor(log x))} )
Is this correct? If correct, can this be optimized?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
使用将索引加倍的方法，直到通过它，然后对刚刚跳过的区域进行二分搜索（看起来您的伪代码正在尝试执行的操作），花费的时间应该是 O(log2 n) 其中 n 是您要搜索的项目的索引。
您将需要 (log2 n) 尝试找到正确的区域，然后 ((log2 n) - 1) 尝试找到
x 在该区域内（因为您已经从 0..n/2 开始搜索，所以您只需要搜索 n/2..n）。因此，O(log2 n + log2 n - 1) = O(log2 n)。但是，如果“无限数组”不包含
x或任何大于x的值，您将永远不会知道，因为您将永远搜索。Using the method of double your index until you pass it, then binary search the region you just jumped over (what it looks like your pseudocode is trying to do), the time spent should be O(log2 n) where n is the index of the item you are searching for.
It will take you (log2 n) tries to find the correct region, and then ((log2 n) - 1) tries to find
xwithin that region (since you already searched from 0..n/2, you only need to search n/2..n). Therefore, O(log2 n + log2 n - 1) = O(log2 n).However, if the "infinite array" does not contain
xor any value greater thanx, you will never know, because you will search forever.排序后的数组确实暴露了这一点：二元排序。
最坏的情况：O(lg(n))。没有更快、更可靠的方法来找到它。
当然，你可以告诉他在无限数组中找到一个元素将花费很长时间。
The sorted array gives it away indeed: binary sort.
Worst case scenario: O(lg(n)). There's no faster, assured way of finding it.
Of course, you could just tell him that finding an element in an infinite array will take forever.