Searching Algorithms · Algoritmos de Busca
| English | Português |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | Busca |
| linear search/ˈlɪnɪə sɜːtʃ/ | busca linear |
| binary search/ˈbaɪnəri sɜːtʃ/ | busca binária |
| sorted/ˈsɔːtɪd/ | ordenado |
Finding a value
- Searching 查找 means locating a target value in a collection.
- Two standard algorithms: linear search 线性查找 and binary search 二分查找.
- Both return the index where the target sits — or a "not found" signal (often
-1). - Which one you may use depends on whether the data is sorted.
Encontrando um valor
- Pesquisar 查找 significa localizar um valor alvo em uma coleção.
- Dois algoritmos padrão: pesquisa linear 线性查找 e pesquisa 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.
Linear search
- Check each element from the start, one by one, until you find the target.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Works on any array — sorted or not.
- Worst case: it looks at every element (
nchecks).
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).
Binary search
- Needs a sorted 已排序 array. Look at the middle element each time.
- If the middle is the target, done. If the target is smaller, search the left half; if larger, the right half.
- Each step halves the range that's left to search.
- Far faster on large sorted arrays — about
log₂ nchecks, notn.
Busca binária
- Precisa de um array ordenado 已排序. Olhe para o elemento meio cada vez.
- 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.
Why binary search is fast
- Linear search of a million items: up to a million checks.
- Binary search of a million sorted items: about 20 checks.
- The catch: the array must already be sorted.
- Halving repeatedly is the big idea behind
O(log n).
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).
Binary search only works on a SORTED array — running it on unsorted data gives wrong answers. It also compares to the middle and throws away half the range each step; a linear search compares from the start and drops just one element. If you're not sure the data is sorted, you must use linear search (or sort first).
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).
Binary search for 7 in [1, 3, 5, 7, 9]:
- Middle is
5(index 2). 7 > 5, so search the right half. - Right half is
[7, 9]; middle is7. Found at index 3. - Two checks instead of four — the range halved each time.
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.
Linear search checks elements from the start (works on any array, up to n checks). Binary search needs a sorted array, compares to the middle, and halves the search range each step (about log₂ n checks). Both return the index found, or a "not found" signal like -1.
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.
Linear vs binary search · Busca linear vs busca binária
Binary search halves the sorted range each step. · A busca binária divide pela metade o intervalo ordenado a cada etapa.
A linear search... · Uma busca linear...
Linear = start to end; works on any array. · Linear = início até fim; funciona em qualquer array.
Binary search requires the array to be... · A busca binária requer que o array seja...
Binary search only works on sorted data. · A busca binária só funciona em dados ordenados.
Each step of binary search... · Cada etapa da busca binária...
It compares to the middle and keeps one half. · Comparar com o meio e manter uma metade.
Binary search in [1,3,5,7,9] for 7: how many comparisons (middle each time)? · Busca binária em [1,3,5,7,9] para 7: quantas comparações (meio a cada vez)?
Compare to 5, then to 7 — two comparisons. · Comparar com 5, depois com 7 — duas comparações.
Binary search gives correct results on an UNSORTED array. · A busca binária fornece resultados corretos em um array NÃO ORDENADO.
It relies on order; unsorted data breaks it. · Ela depende da ordem; dados desordenados a quebram.
Match each search to its property. · Associe cada busca à sua propriedade.
Linear is general but slower; binary is fast but needs order. · Linear é geral mas mais lenta; binária é rápida mas precisa de ordem.