Pesquisa binária em sequências de intervalo desconhecido
Origem: Wikipédia, a enciclopédia livre.
Faz uma busca numa sequência de tamanho indeterminado. Não é possível usar busca binária diretamente, porque busca binária pré-supõe que sabemos o tamanho da sequência.
O que fazer? Encontra um intervalo onde está o elemento procurado, depois aplica busca binária.
1 - Encontra o intervalo que contem o valor procurado:
- Supondo que o elemento procurado seja z e X a sequência ordenada de tamanho desconhecido;
- Procura o elemento X[i], que seja maior ou igual que z;
- Para determinar o índice superior, dobramos a cada passo o limite superior do espaço de busca atual. Até que a afirmação abaixo seja verdadeira:
X[j] <= z <= X[2*j];
- A complexidade da primeira parte é igual a O(log2 j), onde j é o menor índice para o qual z <= X[2*j];
2 - Usa busca binária dentro do intervalo encontrado em 1
- Para localizar o elemento aplica busca binária no intervalo encontrado;
- A complexidade da segunda parte é O(log2 j), pois o intervalo é de tamanho j (2*j - j = j)
