Explique o princípio de funcionamento do algoritmo de busca binária e os seus passos principais.

A pesquisa binária é um algoritmo eficiente para procurar um elemento em um array ordenado. Seu princípio consiste em dividir sequencialmente a área de busca ao meio e comparar o valor buscado com o elemento no meio.

Principais passos:

1. Definir os limites iniciais de busca: índices esquerdo e direito.
2. Encontrar o índice médio: mid = (left + right) // 2.
3. Comparar o valor buscado com o elemento em mid.
   • Se forem iguais, retornar o índice mid.
   • Se o valor buscado for menor, mover o limite direito para mid - 1.
   • Se for maior, mover o limite esquerdo para mid + 1.
4. Repetir os passos 2-3 até que o limite esquerdo ultrapasse o direito.

Se o elemento não for encontrado, retornar, por exemplo, -1.

Exemplo em Python:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1