busca binária multiplicativo - Multiplicative binary search
 Visualização do algoritmo de busca binária multiplicativo, onde 7 é o valor-alvo.
| |
| Classe | algoritmo de busca |
|---|---|
| Estrutura de dados | ordem |
| desempenho de pior caso | O (log n ) |
| desempenho melhor caso | O (1) |
| desempenho médio | O (log n ) |
| complexidade espaço de pior caso | O (1) |
Em ciência da computação , busca binária multiplicativo é uma variação de busca binária que usa uma permutação específica de chaves em uma matriz em vez da ordem de classificação usada por busca binária regular. Busca binária multiplicativo foi primeiramente descrita por Thomas Standish em 1980. Este algoritmo foi originalmente proposto para simplificar o cálculo do índice de ponto médio em pequenos computadores sem operações de divisão ou de mudança eficientes, mas o seu cache de natureza -amigável o torna adequado para pesquisa estática out-of-memory em orientada para o bloco de armazenamento como uma alternativa para árvores B + .
Busca binária multiplicativo é usada por alguns compiladores de otimização para implementar declarações switch .
Algoritmo
Busca binária multiplicativo opera em uma matriz classificada permutado. As chaves são armazenadas na matriz em sequência nível de ordem do equilibrada correspondente árvore de busca binária . Isto coloca o primeiro pivô de uma pesquisa binária como o primeiro elemento na matriz. O segundo eixos estão colocados nas duas posições seguintes.
Dada uma matriz Um dos n elementos com valores Um 0 ... A n -1 , e o valor alvo T , as seguintes sub-rotina usa pesquisa binária multiplicativo para encontrar o índice de T em A .
- Definir i para 0
- Se i ≥ n , a busca termina sem sucesso.
- se A i = T , a pesquisa é feita; voltar i .
- se A i < T , definido i a 2 × i + 1 e vá para o passo 2.
- se A i > T , definido i a 2 × i + 2 e vá para o passo 2.
Veja também
- árvore de busca binária
- Métodos de armazenamento de árvores binárias
- Ahnentafel
- (em espanhol) Pesquisa binária e um programa Java