Búsqueda lineal vs. búsqueda binaria mediante JavaScript

JavaScript viene con algunas herramientas listas para usar bastante útiles para buscar en una matriz. Pero con un conjunto de datos grande, los métodos O(n) como indexOf, findo un bucle básico simplemente no son los mejores o incluso factibles. En cambio, podemos usar la búsqueda binaria para recorrer una matriz sin mirar lo que obviamente no necesitamos, lo que nos da una solución O(logn).

Prerrequisitos

Usaré la notación Big O para comparar el rendimiento y la complejidad, algo que puedes repasar aquí.

Datos de práctica

A continuación se muestran algunos conjuntos de datos ordenados y no ordenados, ambos con 50 elementos, a los que haré referencia.

const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2];const sortedArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50];

Búsqueda lineal

Esta es la solución estándar de fuerza bruta que estoy seguro de que ya ha aplicado miles de veces. Simplemente le decimos: "Necesito algo, así que mire todo uno por uno hasta que lo encuentre". Si hay un millón de veces más elementos, tardará un millón de veces más, algo que nadie va a tolerar. No importa si los datos están ordenados o no.

const linear = (arr, target) = {  let steps = 0;  for (let i = 0; i  arr.length; i++) {    steps++;    if (arr[i] === target) return `Found: ${arr[i]} in ${steps} steps`;  };};console.log(linear(unsortedArr, 40)); // 40 steps in 40 Millisecondsconsole.log(linear(sortedArr, 40)); // 40 steps in 40 Milliseconds

Búsqueda binaria

Obviamente, forzar la obtención de un resultado es una solución muy lenta y no escalable. En lugar de desperdiciar recursos analizando datos que obviamente no son los que queremos, podemos utilizar un enfoque de "dividir y vencer" para que cada operación se centre en ignorar lo que no queremos en lugar de buscar con esfuerzo lo que sí queremos.

Tenemos tres componentes principales, dos punteros y un pivote. Cada puntero comienza en uno de los extremos de la matriz con el pivote en el centro. Luego, verificamos si lo que queremos es más alto o más bajo que nuestro pivote; si es más alto, el puntero izquierdo se mueve a la posición del pivote mientras que el pivote se mueve al nuevo centro. Seguimos ejecutando esto hasta que nuestro pivote sea igual a nuestro objetivo.

Con cada paso, reducimos nuestro conjunto de datos a la mitad, ignorando por completo lo que no necesitamos, lo que nos da una complejidad temporal de O(logn). Si realizáramos una búsqueda de un número en una matriz de un millón de elementos que requiriera diez pasos, una búsqueda de mil millones de elementos podría requerir solo entre 15 y 20 pasos.

const binary = (arr, target) = {  let start = 0;  let end = arr.length;  let pivot = Math.floor((start + end) / 2);  let steps = 0;  for (let i = 0; i  arr.length; i++) {    if (arr[pivot] !== target) {      if (target  arr[pivot]) end = pivot;      else start = pivot;      pivot = Math.floor((start + end) / 2);      steps++;    };    if (arr[pivot] === target) return `Found: ${target} in ${steps} steps`;  };  return 'Nothing Found';};console.log(linear(unsortedArr, 40)); // Nothing Foundconsole.log(binary(arr, 44)); // 5 steps in 8 Millisecondsconsole.log(binary(arr, 43)); // 2 steps in 7 Milliseconds

La búsqueda binaria tiene el gran inconveniente de que solo nos permite hacer esto en matrices ordenadas, pero existen otras soluciones basadas en la preordenación de los datos antes de una búsqueda.

Conclusión

Esta es solo una forma de aplicar una búsqueda binaria, pero la idea se puede reconfigurar para varias estructuras de datos, siempre que estén ordenadas. En el futuro, espero que podamos explorar el uso de esta técnica para recorrer conjuntos de datos más avanzados a velocidades ultrarrápidas ⚡.