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?
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.