Binary Search

Qué es una búsqueda binaria o Binary Search

Binary Search o búsqueda binaria, es una búsqueda también llamada de intervalo medio o logarítmica (de acuerdo a su Big O Notation). Parte de una colección de datos ordenada y busca el punto medio, descartando la parte donde no está el elemento y partiendo de nuevo a la mitad el sub conjunto donde si está.

Supongamos que tenemos el siguiente arreglo de 15 elementos: [1, 3, 4, 7, 9, 11, 13, 16, 19, 18, 20, 22, 24, 27, 30]

• Primero tenemos que asegurarnos que los datos están ordenados, es un requisito. En este caso si lo están, de menor a mayor.
• Necesitamos saber la posición del número 24 dentro del arreglo.

El algoritmo sería el siguiente:

1. Se inicializan 3 variables: indiceInferior con 0, indiceSuperior con el tamaño del arreglo y elementoMedio la mitad entre ambos índices.
2. Si el elemento que está en medio es igual al que buscamos, terminamos el algorirmo.
3. Si es mayor, actualizamos el indiceInferior que toma el valor del elementoMedio
4. Si es menor, actualizamos el indiceSuperior que toma el valor del elementoMedio
5. Volemos a comarar hasta que encontremos el valor deseado o la diferencia entre indiceSuperior–indiceInferior sea menor o igual a 1.

El valor sería encontrado en 3 iteraciones de nuestro algoritmo. Esto nos da una notación de tiempo de O log(n), mucho mas eficiente que la búsqueda lineal que sería O(n). Este tipo de algoritmos también son llamados in place, ya que no requieren estructuras de datos adicionales (otro arreglo) para encontrar el resultado.

var binarySearch = (lookUp) => {
  let numbers = [1, 3, 4, 7, 9, 11, 13, 16, 19, 18, 20, 22, 24, 27, 30];
  let limitLeft = 0;
  let limitRight = numbers.length;
  let index = Math.round(numbers.length / 2);
  let count = 0;
  //Pudiera darse el caso que encontremos el valor deseado incluso antes
  //de iniciar a iterar en nuestro arreglo
  if(numbers[index] === lookUp) {
    return 'Number ' + lookUp + ' found at position ' + index + ' in 0 iterations.';
  } else {
    while(numbers[index] !== lookUp && (limitRight - limitLeft) > 1) {
      //Contador de interaciones
      count++;
      //El número es mas grande que nuestro elemento medio,
      //actualizaremos nuestro límite inferior al punto medio actual
      if(lookUp > numbers[index]) {
        limitLeft = index;
        index += Math.round((limitRight-limitLeft) / 2);
      }
      //El número es mas pequeño que nuestro elemento medio,
      //actualizaremos nuestro límite superior al punto medio actual
      else if(lookUp < numbers[index]) {
        limitRight = index;
        index -= Math.round((limitRight-limitLeft) / 2);
      }
      //Llevamos a cabo la comparación, si el elemento es encontrado,
      //terminamos nuestro ciclo
      if (numbers[index] === lookUp) {
        return 'Number ' + lookUp + ' found at position ' + index + ' in ' + count + ' iterations.';
      }
    }
    //No se encontró el elemento
    return 'Number ' + lookUp + ' not found';
  }
};

 console.log(binarySearch(24));

Aquí una liga con una buena referencia y amplia explicación de la búsqueda binaria.