Algoritmos con Arrays

La palabra «algoritmo» impone, pero es algo que haces a diario: una receta de cocina lo es. Un algoritmo es una serie de pasos que se siguen para resolver un problema. Aquí vamos a escribir un par de ellos con arrays y, de paso, a aprender a medir lo rápidos que son: su complejidad algorítmica.

Algoritmo para encontrar el número mayor#

Primer problema: tienes un array de números y quieres saber cuál es el mayor.

¿Cómo lo harías tú con una lista en papel? Te quedas con el primer número y vas mirando el resto uno a uno. Cada vez que aparece uno más grande, te olvidas del anterior y te quedas con ese. Al llegar al final, el que tienes en la cabeza es el mayor.

La función hace exactamente eso, y la variable max es tu memoria:

function findMaxAlgorithm(array) {  let max = array[0] // recuperamos el primer elemento del array  // recorremos el array desde el segundo elemento  for (let i = 1; i < array.length; i++) {    // ¿es el elemento actual mayor que el máximo?    if (array[i] > max) {      // si es así, lo guardamos como nuevo máximo      max = array[i]    }  }  // devolvemos el máximo número que hemos encontrado  return max;}

Complejidad algorítmica

¿Es rápido este algoritmo? Para responder no se mide el tiempo con un cronómetro, porque depende de cada ordenador. Se cuenta el número de operaciones que hace falta realizar: eso es la complejidad algorítmica.

En nuestro ejemplo no hay atajo posible, porque para estar seguros de cuál es el mayor hay que mirar todos los elementos. Si el array tiene 10 elementos, hacemos 10 comprobaciones. Si tiene 100, hacemos 100. Es decir, el número de operaciones crece al mismo ritmo que el número de elementos del array.

En programación eso se escribe con la notación O(n), donde n es el número de elementos del array.

Así recorre el array el algoritmo, paso a paso:

Búsqueda binaria#

Segundo problema. Tienes un array de números ordenados de menor a mayor, por ejemplo [11, 18, 23, 25, 48, 55, 88, 111, 120], y te pido que busques el 55. ¿Cómo lo harías?

La forma más directa es recorrer el array de principio a fin comparando cada número con el que buscas. Si coincide, lo has encontrado. Si no, pasas al siguiente.

function findNumber(array, number) {  for (let i = 0; i < array.length; i++) {    if (array[i] === number) {      return true    }  }  return false}

Es lo mismo que hace el método .includes(), que es el que deberías usar siempre que puedas. Lo escribimos a mano solo para ver cómo funciona por dentro.

La complejidad de este algoritmo vuelve a ser O(n): en el peor caso, miras todos los elementos. Pero aquí sí podemos hacerlo mejor, porque el array está ordenado.

Piensa en cómo buscas una palabra en un diccionario de papel. No empiezas por la primera página: abres por la mitad, miras si tu palabra va antes o después y descartas de golpe medio diccionario. Eso es la búsqueda binaria, un algoritmo muy popular que encuentra un elemento en un array ordenado en O(log n).

¿Qué significa eso? Que el número de operaciones es el logaritmo del número de elementos. Dicho con números: en un array de 10 elementos, la búsqueda binaria necesita como mucho 4 comprobaciones. En uno de 100, como mucho 7. El array se ha multiplicado por diez y el trabajo apenas ha crecido. ¡Es mucho más rápido!

Implementación de la búsqueda binaria

La idea es ir partiendo el array en dos mitades y quedarte solo con la que te interesa:

1. Mira el elemento que está en la mitad. Si es el que buscas, has terminado.
2. Si el que buscas es mayor, solo puede estar en la mitad derecha. Descarta la izquierda.
3. Si el que buscas es menor, solo puede estar en la mitad izquierda. Descarta la derecha.
4. Repite con la mitad que queda, hasta encontrarlo o quedarte sin elementos.

En el código, index y final marcan los límites del trozo de array donde todavía puede estar el elemento. En cada vuelta, uno de los dos se mueve y el trozo se reduce a la mitad:

function busquedaBinaria(array, elemento) {  let index = 0 // primer elemento del array  let final = array.length - 1 // último elemento del array a buscar    // mientras el índice sea menor o igual que el final  // seguiremos buscando  while (index <= final) {    // calculamos la mitad del array    // como puede ser impar, usamos Math.floor para redondear hacia abajo    const mitad = Math.floor((index + final) / 2)        // si el elemento de la mitad es igual al elemento que estamos buscando    // entonces hemos encontrado el elemento    if (array[mitad] === elemento) {      return mitad    } else if (array[mitad] < elemento) {      // si el elemento de la mitad es menor que      // el elemento que estamos buscando      // entonces tenemos que buscar en la mitad derecha      index = mitad + 1    } else {      // si el elemento de la mitad es mayor que      // el elemento que estamos buscando      // entonces tenemos que buscar en la mitad izquierda      final = mitad - 1    }  }    // si llegamos hasta aquí, es que no hemos encontrado el elemento  // devolvemos -1, para indicar que no se ha encontrado  return -1}

La función devuelve el índice donde está el elemento, o -1 si no lo encuentra. Es el mismo resultado que te da array.indexOf(elemento), el método que JavaScript ya trae para esto y que te recomiendo usar siempre que puedas. De nuevo, escribimos nuestro propio algoritmo por motivos didácticos.