¿Cómo funciona el algoritmo de búsqueda linear?
Imaginémonos que tenemos un arreglo muy grande con el listado de países y deseamos realizar una búsqueda. Para ello la manera mas sencilla es ir valor por valor comparando si el valor en la posición del arreglo es igual al valor buscado hasta encontrar el resultado.
Cuando tenemos valores que no están ordenados (numéricamente o alfabéticamente), esto es una forma común de encontrar valores dentro de un arreglo.
¿Qué funciones de javascript utilizan la búsqueda linear?
Las funciones de javascript que utilizan el algoritmo de búsqueda linear son.
- indexOf
- includes
- find
- findIndex
Ejemplo del uso del algoritmo de búsqueda lineal en javascript
Se requiere una función que cumpla los siguientes requerimientos:
- La función acepta un arreglo y un valor.
- Realiza un recorrido mediante un loop hasta que encuentre el valor en el arreglo.
- Retorna el índice del valor encontrado.
- Si no se encuentra el valor retorna -1.
function busquedaLinear(arr, val) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === val) {
return i;
}
}
return -1;
}
¿Cúal es la complejidad de una búsqueda lineal?
- En el mejor de los casos 0(1).
- En el peor de los casos 0(n).