Jump Search

Qué es el Jump Search

Jump Search es un algoritmo de búsqueda en el cual, en vez de irse de manera secuencial, salta un grupo de elementos de manera repetitiva hasta encontrar el valor buscado o uno mayor. Si se encuentra el valor, termina nuestro algoritmo. Si llegamos a un valor mayor, retrocedemos de uno en uno hasta llegar al valor buscado. Es importante mencionar que el arreglo debe estar ordenado.

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

• Necesitamos saber la posición del número 22 dentro del arreglo.

Cómo determinar el número de elementos a brincar en cada iteración

Usualmente sería √N donde N es el total de elementos. En este caso √15 = 3.87

Redondeando, serían 4.

Con este tamaño de paso y este arreglo en particular, el peor escenario serían 5 iteraciones para encontrar el número 27.

El algoritmo sería el siguiente:

1. Se determina el número de posiciones que estaremos brincando en cada iteración, lo llamaremos x.
2. Inicializamos nuestro apuntador a la posición inicial, lo llamaremos i.
3. Se valida el elemento en la posición i, si es el que buscamos, termina el algoritmo.
4. Si no, brincamos x número de posiciones hacia adelante y volvemos a comparar.
5. Si el número a comparar es mayor al buscado, recorremos hacia atrás desde la posición i hasta encontrar el valor deseado.

El valor sería encontrado en 4 iteraciones de nuestro algoritmo. Esto nos da una notación de tiempo de O (√n). Este tipo de algoritmo es considerado in place, ya que no requiere estructura de dato adicional (otro arreglo) para encontrar el resultado.

var linearSearch = (lookUp) => {
  let numbers = [1, 3, 4, 7, 9, 11, 13, 16, 19, 18, 20, 22, 24, 27, 30];
  let index = 0;
  let count = 0;
  //Determinamos el valor del paso
  let step = Math.round(Math.sqrt(numbers.length));
  do {
    //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.';
    }
    //Si el número evaluado es mayor al buscado, iniciar búsqueda hacia atrás
    if(numbers[index]>lookUp) {
      index--;
      count++;
      do {
        if (numbers[index] === lookUp) {
          return 'Number ' + lookUp + ' found at position ' + index + ' in ' + count + ' iterations.';
        }
      }
      while(numbers[index]>lookUp);
    }
    //Sumamos al índice el valor de la cantidad de pasos a brincar
    index+=step;
    //Contador de iteraciones
    count++;
    //Si el nuevo índice es mayor al total de elementos del arreglo y
    //el último valor del arreglo es mayor al número que buscamos,
    //igualamos el valor del índice al último elemento del arreglo
    if(index>numbers.length && numbers[numbers.length-1]>lookUp) {
      index = numbers.length-1;
    }

  } while(index<numbers.length);

  //No se encontró el elemento
  return 'Number ' + lookUp + ' not found';
};

console.log(linearSearch(22));

Aquí una liga con una buena referencia y amplia explicación de Jump Search.