Configure os parâmetros e clique em Iniciar
Busca Binária
A busca binária é um algoritmo utilizado para encontrar elementos de forma extremamente eficiente em arrays ordenados.
Diferente da busca linear, que percorre os elementos um a um, a busca binária utiliza a ordem dos dados para reduzir drasticamente a quantidade de comparações necessárias.
Conceito
Como funciona
A ideia central da busca binária é simples: sempre olhar para o elemento do meio da estrutura.
A cada passo:
- Verificamos o valor do elemento central
- Se ele for o valor procurado, a busca termina
- Se o valor procurado for menor, continuamos a busca apenas na metade esquerda
- Se for maior, continuamos apenas na metade direita
Como o array está ordenado, metade dos elementos pode ser descartada imediatamente. Em outras palavras, a cada iteração da busca binária o número de possibilidades é reduzido pela metade.
Exemplo
Exemplo
Considere o seguinte array ordenado:
[10, 22, 33, 44, 55, 66, 77]
Se estivermos procurando o valor 44, primeiro verificamos o elemento central.
Caso ele não seja o valor desejado, sabemos exatamente em qual metade do array devemos continuar procurando, descartando todos os outros elementos.
Esse processo continua até que o valor seja encontrado ou não restem mais possibilidades.
Análise
Número de passos
A grande vantagem da busca binária aparece quando analisamos quantos passos são necessários para encontrar um valor.
A cada iteração, o número de elementos considerados é reduzido pela metade. Isso significa que o número de passos cresce muito lentamente, mesmo quando o array aumenta bastante de tamanho.
Por exemplo:
| Número de elementos | Máximo de passos |
|---|---|
| 3 | 2 |
| 8 | 3 |
| 16 | 4 |
| 32 | 5 |
| 1.024 | 10 |
Observe que dobrar o tamanho da estrutura adiciona apenas um passo extra na busca.
Análise
Complexidade
A complexidade da busca binária é:
O(log N)
Isso significa que o número de passos cresce de forma logarítmica em relação ao tamanho da estrutura.
Na prática, isso torna a busca binária extremamente eficiente para grandes volumes de dados.
Requisito fundamental: o array deve estar ordenado!