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.
Dicas
O Haskell tem suporte a muitos tipos de arrays. Este exercício usa arrays imutáveis, boxed e não estritos do Data.Array. Você pode ler mais sobre o uso desses arrays em:
Como uma extensão opcional deste exercício, tente fazer a função find funcionar para arrays com limites arbitrários, por exemplo, arrays em que o primeiro índice não é necessariamente 0.
