Binary Search · Busca Binária
| English | Português |
|---|---|
| sorted/ˈsɔːtɪd/ | ordenado |
| Binary search/ˈbaɪnəri sɜːtʃ/ | Busca binária |
| target/ˈtɑːɡɪt/ | alvo |
| middle/ˈmɪdl/ | meio |
| comparison/kəmˈpærɪsn/ | comparação |
| halves/hɑːvz/ | reduz à metade |
| linear search/ˈlɪnɪə sɜːtʃ/ | busca linear |
Finding fast in a sorted list
- Binary search 二分查找 is a fast way to locate a target 目标 value in a sorted 已排序 list.
- "Sorted" means the values are in order — smallest to largest, say.
- It is far faster than checking every item.
- But it has one strict requirement.
Binary search needs sorted data. On an unsorted list it can jump past the target and miss it. Always sort first — or use a different search.
Encontrando rápido em uma lista ordenada
- Busca binária 二分查找 é uma maneira rápida de localizar um valor alvo 目标 em uma lista ordenada 已排序.
- "Sorted" significa que os valores estão em ordem — do menor para o maior, digamos.
- É muito mais rápida do que verificar cada item.
- Mas ela tem um requisito estrito.
A busca binária precisa de dados ordenados. Em uma lista não ordenada, ela pode pular o alvo e perdê-lo. Sempre ordene primeiro — ou use uma busca diferente.
Binary search can only be used on data that is: · A busca binária só pode ser usada em dados que estão:
On unsorted data it can miss the target. · Em dados desordenados ela pode não encontrar o alvo.
Check the middle, then halve
- The idea is simple: check the middle 中间 element. Then:
- if the middle equals the target, you found it;
- if the target is smaller, search only the left half;
- if the target is larger, search only the right half.
Verifique o meio, depois divida ao meio
- A ideia é simples: verifique o elemento do meio 中间. Então:
- se o meio igualar o alvo, você o encontrou;
- se o alvo for menor, pesquise apenas a metade esquerda;
- se o alvo for maior, pesquise apenas a metade direita.
Linear vs binary search · Busca linear vs busca binária
binary halves the range each step · busca binária reduz o intervalo pela metade a cada passo
Linear search checks every item; binary search halves a sorted list each comparison, so it needs far fewer steps. · A busca linear verifica cada item; a busca binária divide uma lista ordenada pela metade a cada comparação, exigindo muito menos passos.
If the target is larger than the middle element, binary search next looks in the: · Se o alvo for maior que o elemento do meio, a próxima busca binária olha na:
A larger target must be in the right (higher) half. · Um alvo maior deve estar na metade direita (maior).
Each comparison in binary search ______ the remaining part of the list. · Cada comparação na busca binária ______ a parte restante da lista.
Halving each step is why it is so fast. · Dividir pela metade a cada passo é por que é tão rápida.
About how many binary-search checks are needed for a sorted list of 1000 items? (2^10 = 1024) · Aproximadamente quantas verificações de busca binária são necessárias para uma lista ordenada de 1000 itens? (2^10 = 1024)
Because 2^10 = 1024 ≥ 1000, about 10 halvings suffice. · Porque 2^10 = 1024 ≥ 1000, cerca de 10 divisões bastam.
Why it is so fast
- Each comparison 比较 halves 减半 the remaining part of the list.
- For 1000 items, a linear search may need up to 1000 checks.
- Binary search needs at most about 10, because $2^{10} = 1024$.
- The larger the list, the bigger the advantage.
Por que é tão rápida
- Cada comparação 比较 reduz à metade 减半 a parte restante da lista.
- Para 1000 itens, uma busca linear pode precisar de até 1000 verificações.
- A busca binária precisa de no máximo cerca de 10, porque $2^{10} = 1024$.
- Quanto maior a lista, maior a vantagem.
Binary search finds 14 in [2,5,8,11,14,17,20] in how many comparisons? · A busca binária encontra 14 em [2,5,8,11,14,17,20] em quantas comparações?
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons. · Meio 11 → direita; meio 17 → esquerda; meio 14 → encontrado: 3 comparações.
On a large sorted list, binary search needs far fewer comparisons than linear search. · Em uma grande lista ordenada, a busca binária precisa de muito menos comparações do que a busca linear.
Halving beats checking every item one by one. · Dividir pela metade vence verificar cada item um por um.
Versus linear search
- A linear search 线性查找 checks every element one by one.
- Binary search beats it on large sorted lists by halving each step.
Search [2, 5, 8, 11, 14, 17, 20] for 14. Middle is 11; 14 > 11 → search the right half [14, 17, 20]. Middle is 17; 14 < 17 → search [14]. Middle is 14 — found in just 3 comparisons. A linear search would have taken 5.
Versus busca linear
- Uma busca linear 线性查找 verifica cada elemento um por um.
- A busca binária supera a busca linear em listas grandes ordenadas reduzindo à metade a cada etapa.
Pesquise [2, 5, 8, 11, 14, 17, 20] por 14. Meio é 11; 14 > 11 → pesquise a metade direita [14, 17, 20]. Meio é 17; 14 < 17 → pesquise [14]. Meio é 14 — encontrado em apenas 3 comparações. Uma busca linear levaria 5.
Binary search finds a target in a sorted list by checking the middle and keeping only the half that could contain it. Each comparison halves the range, so 1000 items need ~10 checks — far fewer than a linear search's 1000. It works only on sorted data.
Busca binária encontra um alvo em uma lista ordenada verificando o meio e mantendo apenas a metade que poderia contê-lo. Cada comparação reduz à metade o intervalo, então 1000 itens precisam de ~10 verificações — muito menos que as 1000 de uma busca linear. Ela funciona apenas em dados ordenados.