搜索算法及其复杂性 [英] Search algorithm and its complexity

问题描述

有人问我这个问题，在接受采访时：假定一个的无限的是排序整数数组。你将如何寻找该数组的整数？什么是时间复杂度？ 我猜到了由无限意味着面试官是，我们不知道N，其中n是数量最多的数组中的索引值。 我给了以下的答案：

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

这会发现在边界（低和高）（登录X + 1），在最坏的情况下，正值的排序从1开始和随后的数字是因之。 然后二进制搜索要求：

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?

推荐答案

使用双索引的方法，直到你通过它，然后二进制搜索的区域，你只跳过了（它是什么样子的伪code是尝试做），花费的时间应为O（log ₂ n），其中n是您正在搜索的项目的索引。

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(log₂ n) where n is the index of the item you are searching for.

它会带你（日志 ₂ N）试图找到正确的区域，然后（（登录 ₂ N） - 1）试图找到 X 的区域内（因为你已经从0到n / 2搜查，你只需要搜索N /第2..N）。因此，为O（log ₂ N +日志 ₂ N - 1）= O（日志 ₂ N）

It will take you (log₂ n) tries to find the correct region, and then ((log₂ n) - 1) tries to find x within that region (since you already searched from 0..n/2, you only need to search n/2..n). Therefore, O(log₂ n + log₂ n - 1) = O(log₂ n).

但是，如果无限阵列不包含 X 或大于 x值，你会从来不知道，因为你永远搜索

However, if the "infinite array" does not contain x or any value greater than x, you will never know, because you will search forever.

这篇关于搜索算法及其复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！