Como se sabe, o algoritmo de busca binária normal trabalha entre dois índices, que inicialmente são o primeiro e o último índices do array.
Como você está trabalhando com um array infinito, não existe "último índice". Assim sendo, precisamos escolher um índice para ser o índice superior, e a partir daí aplicamos a busca binária normal. Este índice não pode ser totalmente arbitrário. É preciso garantir que o elemento procurado não apareça depois do índice escolhido.
Para preservar a complexidade assintótica da busca binária, pode-se usar o seguinte algoritmo para encontrar um índice superior apropriado em um array infinito:
(Considera-se uma linguagem cujos índices começam em 0
)
declare o índice inferior, inicialmente com 0
declare o índice superior, inicialmente com 2
enquanto o elemento no índice superior for menor que o elemento procurado
o índice inferior recebe o índice superior
o índice superior é dobrado
faça a pesquisa binária normal entre os índices inferior e superior
É muito importante notar que este algoritmo funciona somente se os elementos do array são crescentes, exatamente como exposto na pergunta:
uma seqüência teoricamente infinita x1 < x2 < x3 < x4 < ...
Nem todo array ordenado obedece a essa lei. Por exemplo, um array infinito em que todos os elementos são 1
pode ser considerado ordenado, mas o algoritmo acima vai entrar em loop infinito se o elemento procurado for 2
.