二分查找函数的时间复杂度和空间复杂度

Question

我用Java编写了下面的函数；

int foo(int a[], int n) {
    int num1 = 1, num2 = 1; 
    while(num1 < n) {
        if (binarySearch(a,num1,num2) >= 0) {
            return num2;
        }
        num1 = 2 * num1;
        num2 = 2 * num2;
    }
    return 0;
}

我正在尝试计算这个函数的时间复杂度和空间复杂度。我知道binarySearch的时间复杂度是O(logn)，这个函数的空间复杂度是O(1)。有了这些信息，我试着从foo函数中计算出这些东西。我认为foo的时间复杂度是O((logn)^2)，空间复杂度是O(1)，但我不确定。计算这些东西的最佳方法是什么？

Answer 1

让我们分析一个没有binarySearch()调用的简化while循环：

while(num1 < n) {
    num1 = 2 * num1;
}

作为n的函数，这需要执行多少个步骤

一旦回答了这个问题，最终解决方案的关键就是认识到while循环的复杂性乘以其主体的复杂性。这意味着最终答案就是上述问题时间log n的答案。