Introdução
Deste de caras com um grupo de matemáticos que também são cantores e compositores. Escreveram uma canção para cada um dos seus números preferidos e, como podes imaginar, têm imensos números preferidos (como o 0, o 73 ou o 6174).
Estás curioso por ouvir a canção do teu número preferido. No entanto, com tantas canções para percorrer, encontrar a canção certa podia demorar bastante tempo. Por sorte, organizaram as canções numa lista de reprodução ordenada pelo título, que é simplesmente o número sobre o qual a canção fala.
Dás-te conta de que podes usar um algoritmo de pesquisa binária para encontrar rapidamente uma canção a partir do título.
Instruções
A tua tarefa é implementar um algoritmo de pesquisa binária.
Um algoritmo de pesquisa binária encontra um elemento numa lista dividindo-a repetidamente ao meio e ficando apenas com a metade que contém o elemento que procuramos.
Permite-nos reduzir rapidamente as possíveis localizações do nosso elemento até o encontrarmos, ou até eliminarmos todas as localizações possíveis.
A pesquisa binária só funciona quando a lista está ordenada.
O algoritmo funciona assim:
- Encontra o elemento do meio de uma lista ordenada e compara-o com o elemento que procuramos.
- Se o elemento do meio for o que procuramos, terminámos!
- Se o elemento do meio for maior do que o que procuramos, podemos eliminar esse elemento e todos os elementos a seguir a ele.
- Se o elemento do meio for menor do que o que procuramos, podemos eliminar esse elemento e todos os elementos antes dele.
- Se todos os elementos da lista tiverem sido eliminados, então o elemento não está na lista.
- Caso contrário, repete o processo na parte da lista que ainda não foi eliminada.
Eis um exemplo:
Digamos que procuramos o número 23 na seguinte lista ordenada: [4, 8, 12, 16, 23, 28, 32].
- Começamos por comparar o 23 com o elemento do meio, o 16.
- Como 23 é maior do que 16, podemos eliminar a metade esquerda da lista, ficando com
[23, 28, 32].
- De seguida, comparamos o 23 com o novo elemento do meio, o 28.
- Como 23 é menor do que 28, podemos eliminar a metade direita da lista:
[23].
- Encontrámos o nosso elemento.
