Алгоритм поиска и его сложность

Мне задали этот вопрос в интервью: Предположим, бесконечный массив целых чисел, который сортируется. Как бы вы искали целое число в этом массиве? Какая будет временная сложность? Я догадался, что интервьюер имел в виду под бесконечностью, что мы не знаем значение 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

Это найдет границу (нижнюю и верхнюю) в (log x + 1) времени в худшем случае, когда отсортированные числа начинаются с 1, а последующие числа являются последовательными. Затем для двоичного поиска требуется:

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

Верно? Если верно, можно ли это оптимизировать?