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.
Apêndice
As instruções acima estão sincronizadas com um repositório partilhado para garantir a consistência entre todos os percursos de linguagens.
Este apêndice fornece esclarecimentos adicionais ou modifica as instruções conforme necessário para se alinhar melhor com os objetivos do percurso de Clojure.
Neste exercício do percurso de Clojure, podes assumir que o parâmetro de entrada é um vetor, como indicam os testes.
