Introdução
Você esbarrou em um grupo de matemáticos que também são cantores e compositores. Eles escreveram uma música para cada um dos seus números favoritos e, como você pode imaginar, eles têm muitos números favoritos (como 0, 73 ou 6174).
Você quer ouvir a música do seu número favorito, mas com tanta música para garimpar, encontrar a certa pode demorar um pouco. Felizmente, eles organizaram as músicas em uma playlist ordenada pelo título, que é simplesmente o número sobre o qual a música fala.
Você percebe que pode usar um algoritmo de busca binária para encontrar uma música rapidamente a partir do título.
Instruções
Sua tarefa é implementar um algoritmo de busca binária.
Um algoritmo de busca binária encontra um item em uma lista dividindo-a repetidamente ao meio e mantendo apenas a metade que contém o item que estamos procurando.
Isso nos permite estreitar rapidamente as possíveis localizações do nosso item até encontrá-lo, ou até termos eliminado todas as localizações possíveis.
A busca binária só funciona quando a lista está ordenada.
O algoritmo funciona assim:
- Encontre o elemento do meio de uma lista ordenada e compare-o com o item que estamos procurando.
- Se o elemento do meio for o nosso item, pronto, terminamos!
- Se o elemento do meio for maior que o nosso item, podemos eliminar esse elemento e todos os elementos depois dele.
- Se o elemento do meio for menor que o nosso item, podemos eliminar esse elemento e todos os elementos antes dele.
- Se todos os elementos da lista tiverem sido eliminados, então o item não está na lista.
- Caso contrário, repita o processo na parte da lista que não foi eliminada.
Veja um exemplo:
Digamos que estamos procurando o número 23 na seguinte lista ordenada: [4, 8, 12, 16, 23, 28, 32].
- Começamos comparando 23 com o elemento do meio, 16.
- Como 23 é maior que 16, podemos eliminar a metade esquerda da lista, ficando com
[23, 28, 32].
- Em seguida, comparamos 23 com o novo elemento do meio, 28.
- Como 23 é menor que 28, podemos eliminar a metade direita da lista:
[23].
- Encontramos o nosso item.
Implementação
No Racket, este exercício usa vectors ordenados em vez de listas, porque vectors permitem acesso em tempo constante aos seus elementos.
Assim como em várias outras tracks de Lisp, quando um item não está presente no vector, espera-se que seja retornado o literal Boolean #f em vez de lançar uma exceção.
