java - 循环内二分查找的时间复杂度

Question

我很难确定我的解决方案的时间复杂度是多少。
任务是找到An序列的n值 - 1, 3, 5, 11, 21, 43...

A0 = 1
A1 = 3
An = (An-1)+2*(An-2)

序列“隐藏”在排序数组内。
例如，以下数组 -
1、2、3、4、5、11、17、21 , 40, 65
将返回 4，因为 A4 = 21，而 21 是给定数组中出现的序列的最后一个数字。

对于下一个数组 -
-3、-2、0、10、11、17、21、60
该方法将返回 -1，因为 A0 不在数组中。

我的代码:

public static int elements(int[] arr)
{
    int i=1, j=3, k, tmp;
    int a=-1;
    tmp =indexOf(arr, i);
    if(tmp==-1)
        return a;
    a++;
    tmp=indexOf(arr,j);
    if(tmp==-1)
        return a;
    a++;
    k=(2*i)+j;
    tmp=indexOf(arr,k);

    while(tmp!=-1)
    {
        tmp=indexOf(arr,k);
        a++;
        i=j;
        j=k;
        k=(2*i)+j;
    }
     return a-1;
}

indexOf() 是一个 O(log n) 的二分查找。

Answer 1

在 while 循环中，搜索空间永远不会减少，因为 indexOf 使用相同的参数 arr。在最坏的情况下，这意味着 arr 包含序列 A 的开始间隔，并且使用 n 搜索，其中 n 是 arr 中的元素数量。总的来说，最坏情况下的运行时复杂度为 O(n log n)。