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.
Mensagens de exceção
Às vezes, é necessário lançar uma exceção. Quando você faz isso, deve sempre incluir uma mensagem de erro significativa para indicar qual é a origem do erro. Isso deixa seu código mais legível e ajuda muito na depuração. Em situações em que você sabe que a origem do erro será de um tipo específico, você pode escolher lançar um dos tipos de erro embutidos, mas ainda deve incluir uma mensagem significativa.
Este exercício em particular exige que você use a instrução raise para "lançar" um ValueError quando o valor fornecido não for encontrado no array. Os testes só vão passar se você usar raise na exception e incluir uma mensagem junto.
Para lançar um ValueError com uma mensagem, escreva a mensagem como argumento para o tipo exception:
# example when value is not found in the array.
raise ValueError("value not in array")
