Aula 8: Busca binária

Vamos jogar um jogo de adivinhação: pensei em um número entre 1 e 100, e a cada tentativa eu digo 'muito alto' ou 'muito baixo'. A jogada esperta: chutar sempre o meio e descartar metade das opções. Isso é exatamente a 'busca binária' — um algoritmo que encontra um valor em uma lista ordenada, corta

Busca binária é como procurar uma palavra em um dicionário grosso: você não lê página por página desde o início. Você abre no meio, e se sua palavra vem depois no alfabeto, você descarta toda a primeira metade de uma vez. Cada olhada corta pela metade o que resta para buscar.

busca binária: Um algoritmo de busca em um array ordenado que, a cada passo, verifica o meio e descarta a metade que não pode conter o alvo — O(log n).
tempo logarítmico: O(log n): o número de passos cresce muito devagar — cada vez que n dobra, adiciona-se apenas um passo, porque o espaço de busca é cortado pela metade a cada vez.
espaço de busca: O intervalo de índices [low, high] que ainda pode conter o alvo; a busca binária o reduz pela metade a cada iteração.