A pesquisa binária é uma ferramenta — sua estimativa de complexidade é O(log2(n)), enquanto a busca sequencial convencional tem O(n). Isso significa que, por exemplo, para um array de 1.024 elementos, uma busca linear, no pior caso, quando o elemento desejado não estiver no array, processará todos os 1.024 elementos. A pesquisa binária é suficiente para processar os elementos \(log_2(1024) = 10\). Este resultado é obtido devido ao fato de que após a primeira etapa do loop, a área de busca se reduz a 512 elementos, após a segunda – até 256 etc.
As desvantagens desse algoritmo são a exigência de ordenação de dados, bem como a capacidade de acessar qualquer elemento de dados em um tempo constante (independente da quantidade de dados). Assim, o algoritmo não pode funcionar em arrays não ordenados e quaisquer estruturas de dados baseadas em listas encadeadas.
Implementação
tchau (direita – esquerda > 1) // Desde que a borda direita esteja à direita da esquerda
nc
meio = (esquerda + direita) /< /span> 2; // Meio da área de pesquisa
se (A[meio] >= b) então
direito = meio; // Mova a borda direita
caso contrário
esquerda = meio; // Caso contrário, mova a borda esquerda
cc
se (A[direita] == X) então
saída direita;
caso contrário
saída -1;
onde:
A - matriz de origem,
N - tamanho do array,
X - o número desejado.
|