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.
Restrições
O Rust já disponibiliza na sua biblioteca padrão uma função de pesquisa binária.
Para este exercício, não deves usar essa função. Em vez disso, usa apenas outras ferramentas básicas.
Para pontos bónus
Já tens os testes a passar e o código limpo? Se quiseres, há algumas coisas adicionais que podes experimentar.
- Neste momento, a tua função find provavelmente só funciona com slices de números, mas o sistema de tipos do Rust é suficientemente flexível para criar uma função find que funciona com todos os slices cujos elementos podem ser ordenados.
- Além disso, esta função find pode funcionar não só com slices, mas também, ao mesmo tempo, com um Vec ou um Array.
Para correr os testes bónus, remove a flag #[ignore] e executa os testes com a funcionalidade generic, assim:
$ cargo test --features generic
Depois, partilha a tua opinião num comentário à submissão. Esta experiência tornou o código melhor? Pior? Aprendeste alguma coisa com ela?
