Busca Binária

Leia isso em outras línguas: english. Español.

Em ciência da computação, busca binária, também conhecida como busca de meio-intervalo, busca logarítmica ou corte binário, é um algoritmo de pesquisa que encontra a posição de um elemento alvo dentro de um vetor ordenado. O algoritmo compara o elemento alvo com o elemento central do vetor; se eles são diferentes, a metade em que o elemento alvo não pode estar é eliminada e a busca continua na metade remanescente até que o elemento alvo seja encontrado. Se a busca terminar com a metade remanescente vazia, o elemento alvo não está presente no vetor.

Complexidade

Complexidade de Tempo: O(log(n)) - pois a área de busca é dividida por dois a cada iteração.

Referências

• Wikipedia
• YouTube