Searching algorithms · Algoritmos de búsqueda
| English | Español |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | búsqueda lineal |
| binary search/ˈbaɪnəri sɜːtʃ/ | búsqueda binaria |
Twenty questions for a million names
- A phone book holds a million names. Checking them one at a time, you would expect half a million comparisons before finding the one you want.
- Open it in the middle instead, decide which half the name is in, and throw the other half away. Repeat. You reach any name in twenty comparisons.
- Half a million against twenty is not a small saving; it is the difference between a program that works and one that cannot be used. And it costs one thing: the list must already be in order.
- This lesson is linear search 线性查找 and binary search 二分查找, how each performs, and how to choose.
Veinte preguntas por un millón de nombres
- Un directorio telefónico contiene un millón de nombres. Si los revisa uno a uno, se espera realizar medio millón de comparaciones antes de encontrar el que busca.
- Ábralo en la mitad, decida en qué mitad está el nombre y descarte la otra. Repita. Llega a cualquier nombre en veinte comparaciones.
- Medio millón frente a veinte no es un ahorro menor; es la diferencia entre un programa que funciona y uno que no se puede usar. Y cuesta una cosa: la lista debe estar ya ordenada.
- Esta lección trata sobre la búsqueda lineal 线性查找 y la búsqueda binaria 二分查找, cómo funciona cada una y cómo elegir.
Linear search
- It walks from the start, comparing each element with the target, and stops when it finds a match or reaches the end.
- It works on any list, sorted or not, and on any structure that can be stepped through.
- Worst case: the target is last or absent, so all $n$ elements are compared, which is $O(n)$. On average, about half.
One at a time, from the beginning
Búsqueda lineal
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
- Recorre desde el principio, comparando cada elemento con el objetivo, y se detiene cuando encuentra una coincidencia o llega al final.
- Funciona con cualquier lista, ordenada o no, y con cualquier estructura que pueda ser recorrida paso a paso.
- Peor caso: el objetivo está al final o no existe, por lo que se comparan los $n$ elementos, lo cual es $O(n)$. En promedio, aproximadamente la mitad.
Una a la vez, desde el principio
A linear search: · Una búsqueda lineal:
Linear search needs no preparation and works on any list, at worst O(n). · La búsqueda lineal no necesita preparación y funciona con cualquier lista, como máximo O(n).
Linear search is the better choice when the data is: · La búsqueda lineal es la mejor opción cuando los datos están:
With no order to exploit (or a tiny list), linear search avoids the cost of sorting first. · Sin un orden que aprovechar (o con una lista muy pequeña), la búsqueda lineal evita el costo de ordenar primero.
Binary search
- It requires the data to be sorted. Compare the middle element with the target: if it matches, stop; if the target is larger, discard the lower half; otherwise discard the upper half.
- Each comparison halves the range still to be searched, so the number of comparisons is $O(\log_2 n)$.
- That is why a million items need about twenty comparisons: $2^{20}$ is just over a million.
Búsqueda binaria
low ← 1 ; high ← n
WHILE low <= high DO
mid ← (low + high) DIV 2
IF A[mid] = target THEN
RETURN mid
ENDIF
IF A[mid] < target THEN
low ← mid + 1
ELSE high ← mid - 1
ENDWHILE
RETURN -1
- Requiere que los datos estén ordenados. Compare el elemento central con el objetivo: si coincide, deténgase; si el objetivo es mayor, descarte la mitad inferior; de lo contrario, descarte la mitad superior.
- Cada comparación reduzca a la mitad el rango que queda por buscar, por lo que el número de comparaciones es $O(\log_2 n)$.
- Por eso un millón de elementos necesitan unas veinte comparaciones: $2^{20}$ es apenas más de un millón.
Searching algorithms · Algoritmos de búsqueda
binary halves the range each step · la búsqueda binaria reduce a la mitad el rango en cada paso
Linear search checks every item; binary · binaria halves a sorted list — far fewer comparisons. · Linear revisa cada elemento; binaria divide a la mitad una lista ordenada — mucho menos comparaciones.
The worst-case time complexity of binary search is: · La complejidad temporal en el peor caso de la búsqueda binaria es:
Halving the range each step gives a logarithmic number of comparisons. · Reducir a la mitad el rango en cada paso da un número logarítmico de comparaciones.
About how many comparisons does a binary search need for one million sorted items? · ¿Aproximadamente cuántas comparaciones necesita una búsqueda binaria para un millón de elementos ordenados?
$\log_2(1\,000\,000) \approx 20$ — about 20 comparisons. · $\log_2(1\,000\,000) \approx 20$ — unas 20 comparaciones.
Binary search can be used on any list, sorted or not. · La búsqueda binaria se puede usar en cualquier lista, ordenada o no.
It decides which half to discard by comparing with the middle element, which is only meaningful if the data is in order. · Decide qué mitad descartar comparando con el elemento central, lo cual solo tiene sentido si los datos están en orden.
Binary search is O(log n) because each comparison ____ the range still to be searched. · La búsqueda binaria es O(log n) porque cada comparación ____ el rango restante por buscar.
Twenty halvings take a million down to one, which is why 2^20 being just over a million is the number to remember. · Veinte reducciones a la mitad llevan un millón hasta uno, por eso 2^20, que es ligeramente más de un millón, es el número que hay que recordar.
Worked example: trace a binary search
- The sorted list is 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Trace the search for 23.
lowis 1,highis 10, somidis 5, holding 16. 16 is less than 23, so discard the lower half:lowbecomes 6.low6,high10, somidis 8, holding 56. 56 is greater than 23, sohighbecomes 7.low6,high7, somidis 6, holding 23. Found, in three comparisons where a linear search would have taken six.- Show
low,high,midand the value at each step. Most of the marks are in the trace, not the answer.
Ejemplo resuelto: rastrear una búsqueda binaria
- La lista ordenada es 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Rastree la búsqueda del valor 23.
lowes 1,highes 10, por lo tantomides 5, que contiene 16. 16 es menor que 23, así que se descarta la mitad inferior:lowse convierte en 6.low6,high10, por lo tantomides 8, que contiene 56. 56 es mayor que 23, así quehighse convierte en 7.low6,high7, por lo tantomides 6, que contiene 23. Encontrado, en tres comparaciones donde una búsqueda lineal habría requerido seis.- Muestre
low,high,midy el valor en cada paso. La mayoría de los puntos están en el rastreo, no en la respuesta final.
In the sorted list 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, how many comparisons does a binary search need to find 23? · En la lista ordenada 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, ¿cuántas comparaciones necesita una búsqueda binaria para encontrar 23?
mid 5 holds 16 (too small), mid 8 holds 56 (too large), mid 6 holds 23. A linear search would have taken six. · el medio 5 contiene 16 (demasiado pequeño), el medio 8 contiene 56 (demasiado grande), el medio 6 contiene 23. Una búsqueda lineal habría tardado seis.
Choosing between them
| linear | binary | |
|---|---|---|
| data must be sorted | no | yes |
| comparisons, worst case | $n$ | $\log_2 n$ |
| a million items | up to 1,000,000 | about 20 |
| suits | unsorted or small lists, linked lists | large sorted arrays, searched repeatedly |
- Sorting first costs more than one linear search, so binary search pays only when the list is already sorted or will be searched many times.
- Binary search also needs direct access to the middle element, which an array has and a linked list does not.
Elegir entre ellas
| Lineal | Binaria | |
|---|---|---|
| Los datos deben estar ordenados | no | sí |
| Comparaciones, peor caso | $n$ | $\log_2 n$ |
| Un millón de elementos | hasta 1,000,000 | unas二十 |
| Se adapta a | listas desordenadas o pequeñas, listas enlazadas | arreglos grandes ordenados, buscados repetidamente |
- Ordenar primero cuesta más que una búsqueda lineal, por lo que la búsqueda binaria solo compensa cuando la lista ya está ordenada o será buscada muchas veces.
- La búsqueda binaria también necesita acceso directo al elemento central, algo que tiene un arreglo pero no una lista enlazada.
Worked example: justify the choice
- A program searches an unsorted list of 50 records once. Linear search: sorting the list first would cost far more than the 50 comparisons the search needs.
- A program searches a sorted array of a million records thousands of times a second. Binary search: the data is already sorted and each search costs about 20 comparisons instead of up to a million.
- A program searches a linked list. Linear search: binary search needs to jump straight to the middle element, and a linked list can only be followed from the start.
- Name the algorithm, then the property of the data that decides it.
Ejemplo resuelto: justificar la elección
- Un programa busca una lista desordenada de 50 registros una sola vez. Búsqueda lineal: ordenar la lista primero costaría mucho más que las 50 comparaciones que necesita la búsqueda.
- Un programa busca un arreglo ordenado de un millón de registros miles de veces por segundo. Búsqueda binaria: los datos ya están ordenados y cada búsqueda cuesta unas veinte comparaciones en lugar de hasta un millón.
- Un programa busca en una lista enlazada. Búsqueda lineal: la búsqueda binaria necesita saltar directamente al elemento central, y una lista enlazada solo se puede recorrer desde el principio.
- Nombre el algoritmo, luego la propiedad de los datos que lo decide.
Match each search to its key facts. · Empareja cada búsqueda con sus hechos clave.
Binary search is far faster (O(log n)) but only on sorted data; linear works anywhere at O(n). · La búsqueda binaria es mucho más rápida (O(log n)) pero solo sobre datos ordenados; la lineal funciona en cualquier lugar a O(n).
When is linear search the better choice? Select all · todos that apply. · ¿Cuándo es la búsqueda lineal la mejor opción? Selecciona todas las que correspondan.
The last case is exactly where binary search wins. Sorting first costs more than a single linear search, so it pays only over many searches. · El último caso es exactamente donde gana la búsqueda binaria. Ordenar primero cuesta más que una única búsqueda lineal, así que solo compensa tras muchas búsquedas.
The cost of keeping the file sorted
- Binary search is only available on a sorted list, and that sorting is not free. A question that asks you to justify a choice is asking you to price it.
- If the data is searched often and changed rarely, sort it once and every later search is $\log_2 n$. That is the case for a dictionary or a lookup table.
- If the data changes constantly, every insertion has to keep the order, which costs a shift of the later elements. A linear search over unsorted data can then be the cheaper total.
- Numbers make the argument concrete: a million records need up to a million comparisons linearly, but only 20 by binary search, since $2^{20} > 10^6$.
- So the marked answer names both halves: how often it is searched, and how often it changes.
El costo de mantener el archivo ordenado
- La búsqueda binaria solo está disponible en una lista ordenada, y ese ordenamiento no es gratis. Una pregunta que le pide justificar una elección le está pidiendo que calcule su costo.
- Si los datos se buscan frecuentemente y cambian rara vez, ordénelos una vez y cada búsqueda posterior será $\log_2 n$. Ese es el caso de un diccionario o una tabla de consulta.
- Si los datos cambian constantemente, cada inserción debe mantener el orden, lo cual cuesta un desplazamiento de los elementos posteriores. Entonces, una búsqueda lineal sobre datos desordenados puede tener un costo total menor.
- Los números hacen concreto el argumento: un millón de registros necesitan hasta un millón de comparaciones linealmente, pero solo 20 mediante búsqueda binaria, ya que $2^{20} > 10^6$.
- Por lo tanto, la respuesta marcada menciona ambas mitades: con qué frecuencia se busca y con qué frecuencia cambia.
Put the justification for choosing a search algorithm in order. · Ordena la justificación para elegir un algoritmo de búsqueda.
A justify question wants the trade-off, not the winner. Binary search on a list that changes constantly can cost more in total than a linear search. · Una pregunta de justificación busca el compromiso, no el ganador. La búsqueda binaria en una lista que cambia constantemente puede costar más en total que una búsqueda lineal.
Marks that slip away
- Binary search requires sorted data. Saying "it is faster" without that condition loses the mark.
- Each step halves the range, which is where the $\log_2 n$ comes from. Give the reason, not just the notation.
- Both searches must be able to report not found, which is what the
-1and the loop condition are for. - Binary search needs direct access, so it does not apply to a linked list even if the list is sorted.
Puntos que se pierden fácilmente
- La búsqueda binaria requiere datos ordenados. Decir "es más rápida" sin esa condición hace perder puntos.
- Cada paso reduce a la mitad el rango, de ahí proviene el $\log_2 n$. Dé la razón, no solo la notación.
- Ambas búsquedas deben poder informar "no encontrado", para lo cual sirven el
-1y la condición del bucle. - La búsqueda binaria necesita acceso directo, por lo que no aplica a una lista enlazada incluso si la lista está ordenada.
You've got it
- linear search compares each element from the start, works on any list, and is $O(n)$
- binary search needs sorted data with direct access, compares the middle and halves the range each time, giving $O(\log_2 n)$: about 20 comparisons for a million items
- trace a binary search by showing
low,high,midand the value at each step - choose from the data: unsorted, small or a linked list means linear; large, sorted and searched often means binary
Lo has entendido
- búsqueda lineal compara cada elemento desde el inicio, funciona con cualquier lista, y es $O(n)$
- búsqueda binaria necesita datos ordenados con acceso directo, compara el centro y reduce a la mitad el rango cada vez, dando $O(\log_2 n)$: unas veinte comparaciones para un millón de elementos
- rastree una búsqueda binaria mostrando
low,high,midy el valor en cada paso - elija según los datos: desordenado, pequeño o lista enlazada significa lineal; grande, ordenado y buscado frecuentemente significa binario