Algoritmos III: Busca binária

Bem-vindo à terceira parte da coleção de Algoritmos de Ciência da Computação. Mais uma vez, vamos nos aprofundar em recursão ao abordar o tema de buscas binárias.

Uma "busca binária" é um algoritmo de busca usado em um array que já está ordenado. Ele compara o valor-alvo com o elemento do meio de um array. Se eles não forem iguais, a metade na qual o alvo não pode estar é ignorada e a busca continua na metade restante, novamente usando o elemento do meio para compará-lo com o valor-alvo e repetindo esse processo até que o valor-alvo seja encontrado. Se o valor-alvo não estiver contido no array, eventualmente os índices de busca esquerdo e direito se cruzarão, e essa condição deverá encerrar a busca.

Algoritmo

Para simplificar, vou me referir ao array como "arr", ao índice inicial como "left", ao índice final como "right" e ao elemento que estamos procurando como "elem". Inicialmente, as entradas para left e right serão left = 0 e right = sizeOfArray - 1. O restante do algoritmo pode ser dividido em cinco etapas:

1. Se "left" > "right", a busca deverá terminar sem sucesso.
2. Defina o índice do meio como a divisão inteira para baixo de ("left" + "right") / 2.
3. Se arr(middle) < "elem", defina "left" = middle + 1 e reinicie o algoritmo.
4. Caso contrário, se arr(middle) > "elem", defina "right" = middle - 1 e reinicie o algoritmo.
5. Caso contrário, arr(middle) == "elem" e o item que você está procurando foi encontrado.

Instruções

A função recursiva deste desafio usará uma busca binária para encontrar um elemento em um array fornecido. Se o elemento inserido for encontrado, a função deverá retornar true. Se não conseguir encontrar o elemento, deverá retornar false.

Exemplos

binary_search([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10], left, right, 7) ➞ True

binary_search([1, 11, 14, 15, 32, 64, 67, 88, 92, 94], left, right, 12) ➞ False

binary_search([3, 6, 9, 12, 15, 18, 21, 24, 27, 30], left, right, 27) ➞ True

Observações

• O operador de divisão inteira para baixo em python é //.
• O array será um array de inteiros e todos os inteiros serão positivos.
• Vários dos desafios que serão abordados nesta coleção sobre algoritmos podem ser resolvidos sem recursão e sem implementar os algoritmos descritos em cada desafio. Peço a todos que resolverem esses desafios que o façam conforme o proposto. Não entender os conceitos ensinados será um obstáculo para os desafios posteriores e não ajudará ninguém a avançar em suas habilidades como programador.
• Se você estiver travado, consulte a aba Resources, a aba Comments ou, se estiver realmente travado, use a aba Solutions para desbloquear as respostas.