Searching: linear and binary · Búsqueda: lineal y binaria
Two ways to search
- Searching means finding where a value is in an array (or saying it is not there).
- Linear search checks every item one by one. It works on any array.
- Binary search is much faster but needs the array to be sorted first.
Dos formas de buscar
- Buscar significa encontrar dónde se encuentra un valor en un array (o indicar que no está allí).
- Búsqueda lineal revisa cada elemento uno por uno. Funciona con cualquier array.
- Búsqueda binaria es mucho más rápida, pero requiere que el array esté ordenado primero.
Linear search
- Walk from index
0ton - 1, comparing each item to the target. - Return the index the moment you find it. If you reach the end, return
-1. - For an array of
nitems, this looks at up tonof them.
Búsqueda lineal
- Recorre desde el índice
0hastan - 1, comparando cada elemento con el objetivo. - Devuelve el índice en el momento en que lo encuentres. Si llegas al final, devuelve
-1. - Para un array de
nelementos, esto examina hastande ellos.
Why sorting enables binary search
- If the array is sorted, you can jump to the middle and compare.
- If the middle is too small, the target must be in the right half; if too big, the left half.
- Each step throws away half the array, so it is very fast (about
log2(n)steps).
Por qué el ordenamiento permite la búsqueda binaria
- Si el array está ordenado, puedes saltar a la mitad y comparar.
- Si el valor central es demasiado pequeño, el objetivo debe estar en la mitad derecha; si es demasiado grande, en la mitad izquierda.
- Cada paso descarta la mitad del array, por lo que es muy rápido (aproximadamente
log2(n)pasos).
low, high, mid
- Keep two bounds:
low(start) andhigh(end). The middle ismid = low + (high - low) / 2. - If
a[mid]is the target, returnmid. Ifa[mid] < target, movelow = mid + 1; elsehigh = mid - 1. - Stop when
low > high— the target is not there, so return-1.
low, high, mid
- Mantén dos límites:
low(inicio) yhigh(final). El punto medio esmid = low + (high - low) / 2. - Si
a[mid]es el objetivo, devuelvemid. Sia[mid] < target, muevelow = mid + 1; de lo contrario,high = mid - 1. - Detente cuando
low > high: el objetivo no está ahí, así que devuelve-1.
#include <stdio.h>
int main(void) {
int a[] = {1, 3, 5, 7, 9}; // sorted!
int target = 7, lo = 0, hi = 4, found = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { found = mid; break; }
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
printf("%d\n", found); // 3
return 0;
}
Common mistakes
- Binary search needs a sorted array.
- Linear search checks each element in turn.
Errores comunes
- La búsqueda binaria necesita un array ordenado.
- La búsqueda lineal revisa cada elemento sucesivamente.
Now you try
- For binary search, assume the array is already sorted. Use
low,high, andmid. - Return
-1when the value is not found. Do not write amain— the checker provides one.
Ahora tú intentas
- Para la búsqueda binaria, asume que el array ya está ordenado. Usa
low,highymid. - Devuelve
-1cuando el valor no se encuentre. No escribas una funciónmain— el sistema de verificación proporciona una.
Linear vs binary search · Búsqueda lineal vs. búsqueda binaria
Binary search halves the range each step. · La búsqueda binaria reduce a la mitad el rango en cada paso.
Complete int linear_search(const int a[], int n, int target) so it returns the index of the first target, or -1 if it is not in the array. Do not · no write a main. · Completa int linear_search(const int a[], int n, int target) para que devuelva el índice del primer target, o -1 si no está en el array. No escribas un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Complete int binary_search(const int a[], int n, int target) for a sorted array. Return the index of target, or -1. Use low, high, and mid. Do not · no write a main. · Completa int binary_search(const int a[], int n, int target) para un array ordenado. Devuelve el índice de target, o -1. Usa low, high y mid. No escribas un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.
Complete int first_negative(const int a[], int n) so it returns the index of the first item less than 0, or -1 if there is none. Do not · no write a main. · Completa int first_negative(const int a[], int n) para que devuelva el índice del primer elemento menor que 0, o -1 si no hay ninguno. No escribas un main.
Click Run to see the output here. · Haz clic en Ejecutar para ver la salida aquí.