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.
Restrições
A biblioteca padrão do Rust já traz uma
função de busca binária.
Neste exercício, você não deve usar essa função, e sim outras ferramentas básicas.
Você conseguiu fazer os testes passarem e deixar o código limpo? Se quiser, há
algumas coisas extras que você pode tentar.
- No momento, sua função find provavelmente só funciona com slices de números,
mas o sistema de tipos do Rust é flexível o bastante para criar uma função
find que funcione com todos os slices cujos elementos possam ser ordenados.
- Além disso, essa função find pode funcionar não só com slices, mas ao mesmo
tempo também com um Vec ou um Array.
Para rodar os testes de bônus, remova a flag #[ignore] e execute os testes com
a feature generic, assim:
$ cargo test --features generic
Depois, compartilhe o que você achou em um comentário na solução enviada. Essa
experiência deixou o código melhor? Pior? Você aprendeu alguma coisa com ela?
