Binary Search · Búsqueda binaria
| English | Español |
|---|---|
| sorted/ˈsɔːtɪd/ | ordenados |
| Binary search/ˈbaɪnəri sɜːtʃ/ | Búsqueda binaria |
| target/ˈtɑːɡɪt/ | diana |
| middle/ˈmɪdl/ | del medio |
| comparison/kəmˈpærɪsn/ | comparación |
| halves/hɑːvz/ | se reduce a la mitad |
| linear search/ˈlɪnɪə sɜːtʃ/ | búsqueda lineal |
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.
Encontrar rápido en una lista ordenada
- Búsqueda binaria 二分查找 es una forma rápida de localizar un valor objetivo 目标 en una lista ordenada 已排序.
- "Ordenada" significa que los valores están en orden — de menor a mayor, por ejemplo.
- Es mucho más rápida que revisar cada elemento.
- Pero tiene un requisito estricto.
La búsqueda binaria necesita datos ordenados. En una lista desordenada puede saltarse el objetivo y perderlo. Siempre ordene primero — o use una búsqueda diferente.
Binary search can only be used on data that is: · La búsqueda binaria solo se puede usar en datos que están:
On unsorted data it can miss the target. · En datos desordenados puede no encontrar el objetivo.
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 el medio, luego reduzca a la mitad
- La idea es simple: revise el elemento del medio 中间. Luego:
- si el medio es igual al objetivo, lo encontró;
- si el objetivo es más pequeño, busque solo en la mitad izquierda;
- si el objetivo es más grande, busque solo en la mitad derecha.
Linear vs binary search · Búsqueda lineal vs búsqueda binaria
binary halves the range each step · la búsqueda binaria reduce la mitad del rango en cada paso
Linear search checks every item; binary search halves a sorted list each comparison, so it needs far fewer steps. · La búsqueda lineal revisa cada elemento; la búsqueda binaria divide a la mitad una lista ordenada en cada comparación, por lo que necesita muchos menos pasos.
If the target is larger than the middle element, binary search next looks in the: · Si el objetivo es mayor que el elemento central, la búsqueda binaria busca luego en la:
A larger target must be in the right (higher) half. · Un objetivo mayor debe estar en la mitad derecha (más alta).
Each comparison in binary search ______ the remaining part of the list. · Cada comparación en la búsqueda binaria ______ la parte restante de la lista.
Halving each step is why it is so fast. · Reducir a la mitad en cada paso es por qué es tan rápida.
About how many binary-search checks are needed for a sorted list of 1000 items? (2^10 = 1024) · ¿Aproximadamente cuántas comprobaciones de búsqueda binaria se necesitan para una lista ordenada de 1000 elementos? (2^10 = 1024)
Because 2^10 = 1024 ≥ 1000, about 10 halvings suffice. · Como 2^10 = 1024 ≥ 1000, bastan aproximadamente 10 reducciones a la mitad.
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 qué es tan rápida
- Cada comparación 比较 reduce a la mitad 减半 la parte restante de la lista.
- Para 1000 elementos, una búsqueda lineal puede necesitar hasta 1000 comprobaciones.
- La búsqueda binaria necesita como máximo unas 10, porque $2^{10} = 1024$.
- Cuanto más grande es la lista, mayor es la ventaja.
Binary search finds 14 in [2,5,8,11,14,17,20] in how many comparisons? · La búsqueda binaria encuentra 14 en [2,5,8,11,14,17,20] en cuántas comparaciones?
Middle 11 → right; middle 17 → left; middle 14 → found: 3 comparisons. · Centro 11 → derecha; centro 17 → izquierda; centro 14 → encontrado: 3 comparaciones.
On a large sorted list, binary search needs far fewer comparisons than linear search. · En una lista grande ordenada, la búsqueda binaria necesita mucho menos comparaciones que la búsqueda lineal.
Halving beats checking every item one by one. · Dividir a la mitad supera revisar cada elemento uno por uno.
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.
Frente a la búsqueda lineal
- Una búsqueda lineal 线性查找 revisa cada elemento uno por uno.
- La búsqueda binaria la supera en listas grandes y ordenadas al reducir a la mitad en cada paso.
Buscar [2, 5, 8, 11, 14, 17, 20] para encontrar 14. El medio es 11; 14 > 11 → buscar en la mitad derecha [14, 17, 20]. El medio es 17; 14 < 17 → buscar [14]. El medio es 14 — encontrado en solo 3 comparaciones. Una búsqueda lineal habría tardado 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.
Búsqueda binaria encuentra un objetivo en una lista ordenada verificando el medio y conservando solo la mitad que podría contenerlo. Cada comparación reduce a la mitad el rango, por lo que 1000 elementos necesitan ~10 comprobaciones — mucho menos que las 1000 de una búsqueda lineal. Funciona solo con datos ordenados.