Algoritmos de busca
Introduzido| English | Significado |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | busca linear |
| binary search/ˈbaɪnəri sɜːtʃ/ | busca binária |
Vinte perguntas para um milhão de nomes
- Um livro telefônico contém um milhão de nomes. Verificá-los um de cada vez, espera-se meio milhão de comparações antes de encontrar o que se deseja.
- Abra-o ao meio em vez disso, decida qual metade o nome está, e jogue fora a outra metade. Repita. Você chega a qualquer nome em vinte comparações.
- Meio milhão contra vinte não é uma economia pequena; é a diferença entre um programa que funciona e um que não pode ser usado. E custa uma coisa: a lista já deve estar em ordem.
- Esta aula trata de busca linear e busca binária, seu desempenho e como escolher entre elas.
Busca linear
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
- Ela percorre do início, comparando cada elemento com o alvo, e para quando encontra uma correspondência ou atinge o fim.
- Funciona em qualquer lista, ordenada ou não, e em qualquer estrutura que possa ser percorrida.
- Pior caso: o alvo está no final ou ausente, então todos $n$ elementos são comparados, o que é $O(n)$. Na média, cerca da metade.

Uma de cada vez, do começo
Uma busca linear:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A busca linear não precisa de preparação e funciona em qualquer lista, no pior caso O(n).
A busca linear é a melhor escolha quando os dados são:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Sem ordem para explorar (ou uma lista minúscula), a busca linear evita o custo de ordenar primeiro.
Busca binária
low ← 1 ; high ← n
WHILE low <= high DO
MiddleIndex ← (low + high) DIV 2
IF A[MiddleIndex] = target THEN
RETURN MiddleIndex
ENDIF
IF A[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE high ← MiddleIndex - 1
ENDWHILE
RETURN -1
- Requer que os dados estejam ordenados. Compare o elemento do meio com o alvo: se corresponder, pare; se o alvo for maior, descarte a metade inferior; caso contrário, descarte a metade superior.
- Cada comparação mitade a faixa ainda a ser pesquisada, então o número de comparações é $O(\log_2 n)$.
- É por isso que um milhão de itens precisam de cerca de vinte comparações: $2^{20}$ é pouco mais de um milhão.
Algoritmos de busca
busca binária reduz o intervalo pela metade a cada passo
Linear verifica cada item; binária reduz à metade uma lista ordenada — muito menos comparações.
A complexidade temporal do pior caso da busca binária é:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Reduzir o intervalo pela metade a cada passo resulta em um número logarítmico de comparações.
Aproximadamente quantas comparações uma busca binária precisa para um milhão de itens ordenados?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
$\log_2(1\,000\,000) \approx 20$ — cerca de 20 comparações.
A busca binária pode ser usada em qualquer lista, ordenada ou não.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Ela decide qual metade descartar comparando com o elemento do meio, o que só faz sentido se os dados estiverem em ordem.
A busca binária é $O(\log n)$ porque cada comparação ____ o intervalo restante a ser pesquisado.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Vinte divisões pela metade levam um milhão a um, por isso $2^{20}$, sendo pouco acima de um milhão, é o número a reter.
Exemplo resolvido: rastreie uma busca binária
- A lista ordenada é 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Rastreie a busca por 23.
lowé 1,highé 10, entãomidé 5, contendo 16. 16 é menor que 23, então descarte a metade inferior:lowtorna-se 6.low6,high10, entãomidé 8, contendo 56. 56 é maior que 23, entãohightorna-se 7.low6,high7, entãomidé 6, mantendo 23. Found, em três comparações onde uma pesquisa linear teria demorado seis.- Mostre
low,high,mide o valor em cada etapa. A maioria dos pontos está no rastreamento, não na resposta final.
Na lista ordenada 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, quantas comparações uma busca binária precisa para encontrar 23?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
meio 5 contém 16 (muito pequeno), meio 8 contém 56 (muito grande), meio 6 contém 23. Uma busca linear teria levado seis passos.
Escolhendo entre eles
| linear | binária | |
|---|---|---|
| os dados devem estar ordenados | não | sim |
| comparações, caso pior | $n$ | $\log_2 n$ |
| um milhão de itens | até 1,000,000 | cerca de 20 |
| adequa-se a | listas desordenadas ou pequenas, listas ligadas | grandes arrays ordenados, buscados repetidamente |
- Ordenar primeiro custa mais do que uma única busca linear, então a busca binária só vale a pena quando a lista já está ordenada ou será buscada muitas vezes.
- A busca binária também precisa de acesso direto ao elemento do meio, o que um array tem e uma lista ligada não tem.
Exemplo resolvido: justificar a escolha
- Um programa busca uma lista desordenada de 50 registros uma vez. Busca linear: ordenar a lista primeiro custaria muito mais do que as 50 comparações necessárias para a busca.
- Um programa busca um array ordenado de um milhão de registros milhares de vezes por segundo. Busca binária: os dados já estão ordenados e cada busca custa cerca de 20 comparações em vez de até um milhão.
- Um programa busca uma lista ligada. Busca linear: a busca binária precisa pular diretamente para o elemento do meio, e uma lista ligada só pode ser percorrida do início.
- Nomeie o algoritmo, depois a propriedade do dados que o determina.
Associe cada busca às suas informações-chave.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
A busca binária é muito mais rápida (O(log n)) mas apenas em dados ordenados; a linear funciona em qualquer lugar em O(n).
Quando a busca linear é a melhor escolha? Selecione todas as que se aplicam.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
O último caso é exatamente onde a busca binária vence. Ordenar primeiro custa mais do que uma única busca linear, então compensa apenas sobre muitas buscas.
O custo de manter o arquivo ordenado
- A busca binária só está disponível em uma lista ordenada, e essa ordenação não é gratuita. Uma questão que pede para você justificar uma escolha está pedindo para avaliar seu custo-benefício.
- Se os dados são buscados com frequência e alterados raramente, ordene-os uma vez e toda busca subsequente será $\log_2 n$. Esse é o caso de um dicionário ou tabela de consulta.
- Se os dados mudam constantemente, cada inserção precisa manter a ordem, o que custa um deslocamento dos elementos subsequentes. Uma busca linear sobre dados desordenados pode então ter o custo total menor.
- Números tornam o argumento concreto: um milhão de registros precisam de até um milhão de comparações na linear, mas apenas 20 na binária, pois $2^{20} > 10^6$.
- Então a resposta marcada nomeia ambas as metades: com que frequência é buscada e com que frequência muda.
Coloque a justificativa para escolher um algoritmo de busca em ordem.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
Uma questão de justificar quer saber o trade-off, não o vencedor. A busca binária em uma lista que muda constantemente pode custar mais no total do que uma busca linear.
Marcas que escapam
- A busca binária requer dados ordenados. Dizer "é mais rápida" sem essa condição faz perder o ponto.
- Cada etapa reduz pela metade o intervalo, que é de onde vem o $\log_2 n$. Dê o motivo, não apenas a notação.
- Ambas as buscas devem ser capazes de relatar não encontrado, que é para que servem o
-1e a condição do loop. - A busca binária precisa de acesso direto, então não se aplica a uma lista ligada mesmo que a lista esteja ordenada.
Entendeu?
- busca linear compara cada elemento do início, funciona em qualquer lista, e é $O(n)$
- busca binária precisa de dados ordenados com acesso direto, compara o meio e reduz pela metade o intervalo a cada vez, dando $O(\log_2 n)$: cerca de 20 comparações para um milhão de itens
- rastreie uma busca binária mostrando
low,high,mide o valor em cada etapa - escolha entre os dados: desordenado, pequeno ou uma lista ligada significa linear; grande, ordenado e buscado frequentemente significa binária