A busca binária é um método eficaz que emprega a estratégia de divisão e conquista para encontrar rapidamente um elemento em uma lista ordenada, reduzindo significativamente o espaço de busca pela metade a cada passo. Esta técnica não apenas exemplifica a eficiência algorítmica em resolver problemas de busca, mas também destaca a importância de entender conceitos fundamentais de ciência da computação, como algoritmos de divisão e conquista, que são cruciais para otimização e resolução de problemas complexos de maneira mais intuitiva. O objetivo deste exercício é implementar a busca binária de forma que retorne o índice do elemento buscado na lista (ou -1 se não estiver presente) e o número de passos realizados, fornecendo uma visão clara do processo de divisão e conquista em ação.

Na imagem acima, você encontra uma ilustração do algoritmo em funcionamento.

Entrada Uma lista de inteiros ordenada e um inteiro a ser buscado na lista.

Saída: Uma lista contendo dois elementos: o índice do elemento na lista e o número de passos necessários para encontrar o elemento ou concluir sua ausência.

    assert busca_binaria([1, 2, 3, 4, 5], 3) >> (2, 1)
assert busca_binaria([1, 2, 3, 4, 5], 6) >> (-1, 3)
assert busca_binaria([1, 3, 4, 5, 7, 8, 9], 5) >> (3, 1)