Imagine que você tem uma lista ordenada de números inteiros representando os IDs de produtos de uma loja: lista = [101, 205, 309, 414, 523, 630, 712, 845, 912, 1001] Escreva um algoritmo que utilize busca binária para encontrar a posição (índice) de um ID de produto específico na lista.
Explique como é o processo da busca binária. Por que ela só funciona em listas ordenadas?

Passo 1

Beleza, temos um problema aqui que envolve encontrar a posição de um ID de produto específico em uma lista ordenada. O conteúdo que vamos usar é a busca binária, que é uma técnica eficiente para procurar itens em listas ordenadas. Para resolver isso, vamos precisar entender como a busca binária funciona e por que ela exige que a lista esteja ordenada.

Passo 2

Primeiro, vamos entender o que é a busca binária. Imagine que você tem uma lista ordenada de números e quer encontrar um número específico. Ao invés de verificar cada número um por um (como na busca linear), a busca binária divide a lista ao meio repetidamente para localizar o número mais rápido.

Passo 3

Vamos visualizar isso com a nossa lista de IDs: [101, 205, 309, 414, 523, 630, 712, 845, 912, 1001]. Suponha que queremos encontrar o índice do ID 523.

Passo 4

Começamos comparando o número do meio da lista com o número que estamos procurando. Aqui, a lista tem 10 elementos, então o meio fica entre o 5º e o 6º elemento. Vamos escolher o 5º elemento para simplificar, que é 523.

Passo 5

Agora, comparamos 523 com o número que queremos encontrar (523). Como eles são iguais, encontramos o número na posição 4 (lembrando que os índices começam em 0).

Passo 6

Se o número do meio não fosse igual ao que estamos procurando, decidiríamos se devemos procurar na metade esquerda ou na metade direita da lista. Isso só funciona porque a lista está ordenada; sem essa ordem, não saberíamos qual metade escolher.

Passo 7

Agora, vamos escrever um algoritmo simples de busca binária:
def busca_binaria(lista, alvo):
    inicio = 0
    fim = len(lista) - 1

    while inicio <= fim:
        meio = (inicio + fim) // 2
        if lista[meio] == alvo:
            return meio
        elif lista[meio] < alvo:
            inicio = meio + 1
        else:
            fim = meio - 1
    return -1  # Se não encontrado

Resposta

Usando a busca binária, o ID 523 está na posição de índice 4 na lista.

Exercícios relacionados