Búsqueda binaria en JavaScript

La búsqueda binaria es un algoritmo de búsqueda que se utiliza para encontrar la posición de un elemento específico en una lista ordenada. Funciona dividiendo repetidamente la lista por la mitad, hasta que se encuentra el elemento deseado o se determina que el elemento no está presente en la lista.

¿Cómo funciona la búsqueda binaria?

Para entender cómo funciona la búsqueda binaria, consideremos un ejemplo. Supongamos que tenemos una lista ordenada de enteros y queremos encontrar la posición del número 37. Así es como funcionaría el algoritmo de búsqueda binaria:

1. Primero, determinamos el elemento medio de la lista. Si el elemento del medio es 37, hemos terminado y devolvemos la posición del elemento.
2. Si el elemento del medio no es 37, comprobamos si es mayor o menor que 37. Si es mayor que 37, sabemos que el elemento deseado debe estar en la mitad izquierda de la lista. Si es menor de 37, sabemos que el elemento deseado debe estar en la mitad derecha de la lista.
3. Repetimos el proceso en la mitad apropiada de la lista hasta que se encuentra el elemento o se determina que el elemento no está presente en la lista.

function binarySearch(arr, x) {
  let start = 0;
  let end = arr.length - 1;
  
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    
    if (arr[mid] === x) {
      return mid;
    }
    else if (arr[mid] < x) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    }
  }
  
  return -1;
}

let arr = [1, 3, 5, 7, 9, 11, 13];
let x = 5;

console.log(binarySearch(arr, x)); // Output: 2

¿Por qué deberíamos usar la búsqueda binaria?

Entonces, ¿por qué deberíamos usar la búsqueda binaria? Una de las principales ventajas de la búsqueda binaria es su complejidad temporal. En el peor de los casos, la complejidad temporal de la búsqueda binaria es O(log n), lo que significa que es mucho más rápida que la búsqueda lineal (O(n)) para listas grandes. Esto lo convierte en un algoritmo eficiente para buscar grandes conjuntos de datos.

En conclusión, la búsqueda binaria es un algoritmo útil para encontrar rápidamente la posición de un elemento específico en una lista ordenada. Su complejidad de tiempo lo hace adecuado para buscar grandes conjuntos de datos y es relativamente fácil de implementar en JavaScript.