Searching Algorithms · Algoritmos de búsqueda
| English | Español |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | Búsqueda |
| linear search/ˈlɪnɪə sɜːtʃ/ | búsqueda lineal |
| binary search/ˈbaɪnəri sɜːtʃ/ | búsqueda binaria |
| sorted/ˈsɔːtɪd/ | ordenados |
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.
Encontrar un valor
- Buscar 查找 significa localizar un valor objetivo en una colección.
- Dos algoritmos estándar: búsqueda lineal 线性查找 y búsqueda binaria 二分查找.
- Ambos devuelven el índice donde se encuentra el objetivo — o una señal de "no encontrado" (a menudo
-1). - Cuál usar depende de si los datos están 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).
Búsqueda lineal
- Revisa cada elemento desde el inicio, uno por uno, hasta encontrar el objetivo.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Funciona con cualquier array — ordenado o no.
- Peor caso: revisa todos los elementos (
ncomprobaciones).
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.
Búsqueda binaria
- Requiere un array ordenado 已排序. Mira el elemento del medio cada vez.
- Si el medio es el objetivo, terminó. Si el objetivo es más pequeño, busca en la mitad izquierda; si es más grande, en la mitad derecha.
- Cada paso reduz a la mitad el rango que queda por buscar.
- Mucho más rápido en arrays grandes ordenados: unas
log₂ ncomprobaciones, non.
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 qué la búsqueda binaria es rápida
- Búsqueda lineal de un millón de elementos: hasta un millón de comprobaciones.
- Búsqueda binaria de un millón de elementos ordenados: unas 20 comprobaciones.
- El requisito: el array debe estar ya ordenado.
- Reducir a la mitad repetidamente es la idea clave detrás de
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).
La búsqueda binaria solo funciona en un array ORDENADO — ejecutarla sobre datos desordenados da respuestas incorrectas. También compara con el medio y descarta la mitad del rango en cada paso; una búsqueda lineal compara desde el inicio y elimina solo un elemento. Si no estás seguro de que los datos estén ordenados, debes usar búsqueda lineal (o ordenarlos primero).
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.
Búsqueda binaria para el 7 en [1, 3, 5, 7, 9]:
- El medio es
5(índice 2). Como 7 > 5, busca en la mitad derecha. - La mitad derecha es
[7, 9]; el medio es7. Encontrado en el índice 3. - Dos comprobaciones en lugar de cuatro — el rango se redujo a la mitad 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.
Búsqueda lineal revisa elementos desde el inicio (funciona en cualquier array, hasta n comprobaciones). Búsqueda binaria necesita un array ordenado, compara con el medio y reduce a la mitad el rango de búsqueda en cada paso (unas log₂ n comprobaciones). Ambos devuelven el índice encontrado, o una señal de "no encontrado" como -1.
Linear vs binary search · Búsqueda lineal vs binaria
Binary search halves the sorted range each step. · La búsqueda binaria reduce a la mitad el rango ordenado en cada paso.
A linear search... · Una búsqueda lineal...
Linear = start to end; works on any array. · Lineal = de principio a fin; funciona con cualquier array.
Binary search requires the array to be... · La búsqueda binaria requiere que el array esté...
Binary search only works on sorted data. · La búsqueda binaria solo funciona con datos ordenados.
Each step of binary search... · Cada paso de la búsqueda binaria...
It compares to the middle and keeps one half. · Compara con el medio y mantiene una mitad.
Binary search in [1,3,5,7,9] for 7: how many comparisons (middle each time)? · Búsqueda binaria en [1,3,5,7,9] para 7: ¿cuántas comparaciones (mitad cada vez)?
Compare to 5, then to 7 — two comparisons. · Comparar con 5, luego con 7 — dos comparaciones.
Binary search gives correct results on an UNSORTED array. · La búsqueda binaria da resultados correctos en un array NO ORDENADO.
It relies on order; unsorted data breaks it. · Depende del orden; los datos desordenados la rompen.
Match each search to its property. · Empareja cada búsqueda con su propiedad.
Linear is general but slower; binary is fast but needs order. · La lineal es general pero más lenta; la binaria es rápida pero necesita orden.