Algoritmos de Busca
Introduzido| English | Significado |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | Searching: busca |
| linear search/ˈlɪnɪə sɜːtʃ/ | Busca linear |
| binary search/ˈbaɪnəri sɜːtʃ/ | binary search: busca binária |
| sorted/ˈsɔːtɪd/ | sorted: ordenado |
Encontrando um valor
- Pesquisa significa localizar um valor-alvo em uma coleção.
- Dois algoritmos padrão: busca linear e busca binária.
- Ambos retornam o índice onde o alvo está — ou um sinal de "não encontrado" (geralmente
-1). - Qual deles você pode usar depende se os dados estão ordenados.
Busca linear
- Verifique cada elemento do início, um por um, até encontrar o alvo.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Funciona em qualquer array — ordenado ou não.
- Pior caso: olha para todos os elementos (
nverificações).

A busca linear verifica cada elemento sucessivamente até encontrar o alvo

A busca binária reduz pela metade o intervalo em cada passo
Busca binária
- Necessita de um array ordenado. Observe o elemento central em cada etapa.
- Se o meio for o alvo, pronto. Se o alvo for menor, pesquise a metade esquerda; se maior, a metade direita.
- Cada passo divide ao meio o intervalo restante para pesquisa.
- Muito mais rápido em arrays grandes ordenados — cerca de
log₂ nverificações, nãon.
Por que a pesquisa binária é rápida
- Pesquisa linear de um milhão de itens: até um milhão de verificações.
- Pesquisa binária de um milhão de itens ordenados: cerca de 20 verificações.
- O detalhe: o array deve já estar ordenado.
- Dividir repetidamente ao meio é a grande ideia por trás do
O(log n).
A pesquisa binária só funciona em um array ORDENADO — executá-la em dados desordenados dá respostas erradas. Ela também compara com o meio e descarta metade do intervalo a cada passo; uma pesquisa linear compara a partir do início e descarta apenas um elemento. Se você não tiver certeza de que os dados estão ordenados, deve usar pesquisa linear (ou ordenar primeiro).
Pesquisa binária para 7 em [1, 3, 5, 7, 9]:
- O meio é
5(índice 2). 7 > 5, então pesquise a metade direita. - A metade direita é
[7, 9]; o meio é7. Encontrado no índice 3. - Duas verificações em vez de quatro — o intervalo foi dividido ao meio a cada vez.
Pesquisa linear verifica elementos a partir do início (funciona em qualquer array, até n verificações). Pesquisa binária precisa de um array ordenado, compara com o meio e divide ao meio o intervalo de pesquisa a cada passo (cerca de log₂ n verificações). Ambos retornam o índice encontrado, ou um sinal de "não encontrado" como -1.
Busca linear vs busca binária
A busca binária divide pela metade o intervalo ordenado a cada etapa.
Uma busca linear...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Linear = início até fim; funciona em qualquer array.
A busca binária requer que o array seja...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A busca binária só funciona em dados ordenados.
Cada etapa da busca binária...
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Comparar com o meio e manter uma metade.
Busca binária em [1,3,5,7,9] para 7: quantas comparações (meio a cada vez)?
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Comparar com 5, depois com 7 — duas comparações.
A busca binária fornece resultados corretos em um array NÃO ORDENADO.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Ela depende da ordem; dados desordenados a quebram.
Associe cada busca à sua propriedade.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Linear é geral mas mais lenta; binária é rápida mas precisa de ordem.