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.
Implementação
Em Racket, usam-se vetores ordenados em vez de listas, porque os vetores permitem acesso em tempo constante aos seus elementos.
Tal como em várias outras tracks de Lisp, quando um item não está presente no vetor, espera-se que o literal Boolean #f seja devolvido em vez de lançar uma exceção.
