Saltar búsqueda en Java

Jump Search es un algoritmo bastante eficiente para buscar matrices ordenadas saltando a través de bloques. En este artículo, implementaremos Jump Search en Java y realizaremos un análisis Big-O.

Introducción

Ya sea buscando en una lista de reproducción su canción favorita o buscando en un catálogo para elegir el restaurante para su próxima comida, nuestras vidas están llenas de búsqueda de cosas.

De la misma manera, las computadoras realizan consultas de búsqueda en sus colecciones y estructuras de datos. Sin embargo, a diferencia de los humanos, las computadoras tienen que realizar búsquedas en conjuntos de datos mucho más grandes en tiempos que son órdenes de magnitud más rápidos que los humanos.

Esto llevó a los científicos informáticos a idear muchos algoritmos de búsqueda, donde cada uno suele ser más óptimo que otro en ciertas colecciones.

Saltar búsqueda

Jump Search (también conocido como Block Search) es un algoritmo que se utiliza para buscar la posición de un elemento de destino en una colección o estructura de datos ordenados.

En lugar de buscar en la matriz elemento por elemento (búsqueda lineal), la búsqueda por salto evalúa bloques de elementos. O más bien, ya que es una matriz ordenada: el elemento con el valor más alto en cada bloque.

Si el valor es menor que el elemento de destino, se considera el siguiente bloque.
Si el valor es mayor que el elemento de destino, el elemento de destino está en el bloque actual.
Si el valor es el elemento de destino, simplemente devuélvalo.

Cambiando iterativamente, o más bien saltando hacia adelante, encontraremos el elemento objetivo o llegaremos al final de la colección sin encontrarlo.

Aquí hay una representación visual de cómo funciona Jump Search:

jump search visualization gif

Evidentemente, Jump Search siempre busca hacia adelante en sus matrices, a diferencia de los métodos de búsqueda de ida y vuelta como Binary Search. Este comportamiento hace que Jump Search sea mucho más eficiente para realizar búsquedas en datos almacenados en unidades físicas con medios giratorios.

Además, otra forma de entender esta búsqueda es sin bloques: simplemente hay un Jump Gap entre los elementos evaluados. No se guarda ningún bloque real en la memoria mientras se ejecuta el algoritmo.

Implementación

Dicho esto, implementemos Jump Search. Hay dos enfoques que puede tomar, sin un "ganador" real entre estos dos: la implementación iterativa y recursiva.

Elegir entre estos dos depende de usted y, a menos que esté trabajando en conjuntos de datos increíblemente enormes, no debería haber una diferencia en el rendimiento. La recursividad conduce a un mayor uso del espacio de memoria/procesador, pero normalmente es más limpio para leer y escribir.

Por otra parte, si está trabajando en conjuntos de datos realmente grandes, probablemente usaría algoritmos de búsqueda optimizados y más eficientes.

Implementación iterativa {#implementación iterativa}

Dicho esto, comencemos con el enfoque iterativo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public static int jumpSearch(int[] arrayToSearch, int element) {
    int blockSize = (int) Math.floor(Math.sqrt(arrayToSearch.length));

    int currentLastIndex = blockSize-1;
    
    // Jump to next block as long as target element is > currentLastIndex
    // and the array end has not been reached
    while (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) {
        currentLastIndex += blockSize;
    }

    // Find accurate position of target element using Linear Search
    for (int currentSearchIndex = currentLastIndex - blockSize + 1;
         currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) {
        if (element == arrayToSearch[currentSearchIndex]) {
            return currentSearchIndex;
        }
    }
    // Target element not found. Return negative integer as element position.
    return -1;
}

En primer lugar, hemos calculado el tamaño del bloque. Generalmente, una raíz cuadrada de la longitud de la matriz es un buen tamaño para elegir. Esto se explica con más detalle en la sección Análisis Big-O. Buscar a través de un bloque como este, al final, también será barato para un algoritmo como la búsqueda lineal.

Dado que la matriz está ordenada, si el valor de nuestro elemento de destino es mayor que el valor del elemento actual, entonces el elemento de destino seguramente no puede estar dentro del bloque actual. Así que saltamos al siguiente bloque y comparamos el elemento de destino con el valor del último elemento de índice del nuevo bloque.

Este salto se repite hasta encontrar el bloque que contiene el elemento objetivo.

Si el elemento de destino ya no es mayor que el valor del último elemento en un bloque, entonces tiene que estar dentro del bloque si es que existe.

Entonces encontraremos la posición precisa del elemento objetivo usando la Búsqueda lineal

Si llegamos al final de la matriz sin encontrar un bloque que contenga nuestro elemento de destino, no está presente en la matriz y devolvemos -1 para indicarlo.

Implementación recursiva {#implementación recursiva}

Con la implementación iterativa fuera del camino, exploremos también la implementación recursiva:

 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
public static int jumpSearchInit(int[] arrayToSearch, int element) {
    int blockSize = (int) Math.sqrt(arrayToSearch.length);

    // Hold the last index of the current block
    int currentLastIndex = blockSize-1;

    return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex);
}

public static int jumpSearch(int[] arrayToSearch, int element, int blockSize, int currentLastIndex) {
    if (currentLastIndex < arrayToSearch.length && element > arrayToSearch[currentLastIndex]) {
        currentLastIndex += blockSize;
        // Make recursive call to jumpSearch method
        return jumpSearch(arrayToSearch, element, blockSize, currentLastIndex);
    } else {
        // Find accurate position of target element using linear search
        for (int currentSearchIndex = currentLastIndex - blockSize + 1;currentSearchIndex <= currentLastIndex && currentSearchIndex < arrayToSearch.length; currentSearchIndex++) {
            if (element == arrayToSearch[currentSearchIndex]) {
                return currentSearchIndex;
            }
        }
    }
    // Target element not found. Return negative integer as element position.
    return -1;
}

La realización recursiva de una búsqueda por salto funciona de la misma manera. Simplemente llamamos al método recursivamente en lugar de tener un bucle while.

Necesitamos el uso de un método de inicialización para hacer algunos cálculos iniciales. Es decir, el tamaño de bloque óptimo y el último índice del primer bloque.

A partir de entonces, siempre que nuestro elemento de destino sea mayor que el valor del último elemento de índice del bloque actual, llamamos recursivamente al método Jump Search y le pasamos los parámetros del bloque subsiguiente.

Esta recursión finaliza una vez que se encuentra el bloque que contiene el elemento de destino, o si finalmente se alcanza el final de la matriz

En caso de que se encuentre un bloque de destino de este tipo, realizamos una búsqueda lineal en él para encontrar la posición del elemento de destino.

Benchmarking Jump Search

Hagamos un benchmark de Jump Search ejecutándolo contra arreglos de enteros ordenados de varios tamaños. Por supuesto, buscaremos el peor de los casos en todos estos (el último elemento):


Tamaño de matriz 1.ª ejecución (ms) 2.ª ejecución (ms) 3.ª ejecución (ms) Promedio (ms) 10 0,3595 0,2267 0,3477 0,3119 10.000 0,2210 0,5809 0,2225 0,3410 1.000.000 0,7754 0,7788 0,7906 0,7816


Comparado con la búsqueda lineal que toma 5.4209ms, es evidente que la búsqueda por salto es significativamente más rápida.

Análisis O grande

Considere una matriz de enteros ordenados de tamaño n con un tamaño de bloque de m.

En el mejor de los casos, Jump Search encontraría el elemento de destino en el borde del primer bloque en el que busca. A su vez, esto hace que Jump Search tenga una eficiencia en el mejor de los casos de complejidad O(1) en Términos de notación Big-O.

Por el contrario, considerando el peor de los casos, Jump Search saltaría consecutivamente hasta su último bloque en busca del elemento de destino, lo que a su vez provocaría un número de saltos n/m. Además, si el valor del último elemento de este bloque fuera mayor que el elemento de destino, Jump Search realizaría una búsqueda lineal con iteraciones m-1.

Esto hace que Jump Search realice saltos (n/m) con iteraciones m-1 adicionales. Este valor es mínimo en m = √n. Por lo tanto, el tamaño de bloque óptimo es √n.

En consecuencia, Jump Search mantiene una eficiencia promedio y en el peor de los casos de complejidad O(√n).

Esto hace que sea digno de mención que aunque Jump Search es altamente eficiente para buscar matrices, especialmente cuando su comportamiento de búsqueda directa es favorable, su rendimiento promedio lo ubica en algún lugar entre Búsqueda binaria con su complejidad O(log n) y Búsqueda lineal con una complejidad O(n).

Y también, Jump Search requiere constantemente que las matrices buscadas se clasifiquen en orden ascendente, por adelantado.

Conclusión

Jump Search se realiza saltando adelante bloque por bloque de la matriz hasta que se encuentra un bloque que podría contener un elemento determinado.

En este artículo, implementamos Jump Search iterativo y recursivo y comparamos el algoritmo con matrices de diferentes tamaños.

Además, llevamos a cabo un análisis Big-O que demuestra cómo Jump Search adquirió su eficiencia promedio y en el peor de los casos de O(√n).