Algoritmos de búsqueda en Java

La búsqueda es una de las acciones más comunes que se realizan en las aplicaciones comerciales habituales. Esto implica obtener algunos datos almacenados en estructuras de datos como Arrays,...

Introducción

La búsqueda es una de las acciones más comunes que se realizan en las aplicaciones comerciales habituales. Esto implica obtener algunos datos almacenados en estructuras de datos como Arrays, List, Map, etc. La mayoría de las veces, esta operación de búsqueda determina la capacidad de respuesta de la aplicación para el usuario final.

En este artículo, echemos un vistazo a algunas de las estrategias de búsqueda que se pueden usar para atender diferentes escenarios. También los implementaremos en Java y analizaremos su rendimiento con algunos parámetros conocidos como Complejidad de tiempo y espacio.

Búsqueda lineal

Búsqueda lineal o secuencial es el más simple de los algoritmos de búsqueda. Si bien ciertamente es el más simple, definitivamente no es el más común debido a su ineficiencia. Es un algoritmo de fuerza bruta. Muy rara vez se usa en producción y, en la mayoría de los casos, es superado por otros algoritmos.

La búsqueda lineal no tiene requisitos previos para el estado de la estructura de datos subyacente.

Explicación

La búsqueda lineal implica la búsqueda secuencial de un elemento en la estructura de datos dada hasta que se encuentra el elemento o se alcanza el final de la estructura.

Si se encuentra el elemento, generalmente solo devolvemos su posición en la estructura de datos. Si no, normalmente devolvemos -1.

Implementación

Ahora veamos cómo implementar la búsqueda lineal en Java:

1
2
3
4
5
6
7
8
public static int linearSearch(int arr[], int elementToSearch) {

    for (int index = 0; index < arr.length; index++) {
        if (arr[index] == elementToSearch)
            return index;
    }
    return -1;
}

Para probarlo, usaremos una matriz simple de enteros:

1
2
int index = linearSearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
print(67, index);

Con un método de ayuda simple para imprimir el resultado:

1
2
3
4
5
6
7
8
public static void print(int elementToSearch, int index) {
    if (index == -1){
        System.out.println(elementToSearch + " not found.");
    }
    else {
        System.out.println(elementToSearch + " found at index: " + index);
    }
}

Producción:

1
67 found at index: 8

Complejidad del tiempo

Aquí estamos iterando a través del conjunto completo de elementos N secuencialmente para obtener la ubicación del elemento que se busca. El peor caso para este algoritmo será si el elemento que estamos buscando es el último elemento de la matriz.

En este caso, iteramos N veces antes de encontrar el elemento.

Por lo tanto, la complejidad temporal de la búsqueda lineal es O(N).

Complejidad espacial

Este tipo de búsqueda requiere solo una unidad de memoria para almacenar el elemento que se busca. Esto no es relevante para el tamaño de la matriz de entrada.

Por lo tanto, la complejidad espacial de la búsqueda lineal es O(1).

Aplicaciones

La búsqueda lineal se puede utilizar para buscar en un conjunto de datos pequeño y desordenado que se garantiza que no aumentará mucho de tamaño.

Es un algoritmo de búsqueda muy básico pero debido a su aumento lineal en la complejidad del tiempo, no encuentra aplicación en muchos sistemas de producción.

Búsqueda binaria

Búsqueda binaria o logarítmica es uno de los algoritmos de búsqueda más utilizados principalmente debido a su rápido tiempo de búsqueda.

Explicación

Este tipo de búsqueda utiliza la metodología Divide and Conquer y requiere que el conjunto de datos se ordene de antemano.

Divide la colección de entrada en mitades iguales, y con cada iteración compara el elemento objetivo con el elemento en el medio.

Si se encuentra el elemento, la búsqueda finaliza. De lo contrario, continuamos buscando el elemento dividiendo y seleccionando la partición apropiada de la matriz, en función de si el elemento objetivo es más pequeño o más grande que el elemento del medio.

Por eso es importante tener una colección ordenada para la búsqueda binaria.

La búsqueda termina cuando firstIndex (nuestro puntero) pasa lastIndex (último elemento), lo que implica que hemos buscado en toda la matriz y el elemento no está presente.

Hay dos formas de implementar este algoritmo: iterativo y recursivo.

No debería haber una diferencia con respecto a la complejidad de tiempo y espacio entre estas dos implementaciones, aunque esto no es cierto para todos los idiomas.

Implementación

Iterativo

Primero echemos un vistazo al enfoque iterativo:

 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
public static int binarySearch(int arr[], int elementToSearch) {

    int firstIndex = 0;
    int lastIndex = arr.length - 1;

    // termination condition (element isn't present)
    while(firstIndex <= lastIndex) {
        int middleIndex = (firstIndex + lastIndex) / 2;
        // if the middle element is our goal element, return its index
        if (arr[middleIndex] == elementToSearch) {
            return middleIndex;
        }

        // if the middle element is smaller
        // point our index to the middle+1, taking the first half out of consideration
        else if (arr[middleIndex] < elementToSearch)
            firstIndex = middleIndex + 1;

        // if the middle element is bigger
        // point our index to the middle-1, taking the second half out of consideration
        else if (arr[middleIndex] > elementToSearch)
            lastIndex = middleIndex - 1;

    }
    return -1;
}

Podemos usar el algoritmo así:

1
2
int index = binarySearch(new int[]{89, 57, 91, 47, 95, 3, 27, 22, 67, 99}, 67);
print(67, index);

Producción:

1
67 found at index: 5
Recursivo

Y ahora echemos un vistazo a 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
public static int recursiveBinarySearch(int arr[], int firstElement, int lastElement, int elementToSearch) {

    // termination condition
    if (lastElement >= firstElement) {
        int mid = firstElement + (lastElement - firstElement) / 2;

        // if the middle element is our goal element, return its index
        if (arr[mid] == elementToSearch)
            return mid;

        // if the middle element is bigger than the goal element
        // recursively call the method with narrowed data
        if (arr[mid] > elementToSearch)
            return recursiveBinarySearch(arr, firstElement, mid - 1, elementToSearch);

        // else, recursively call the method with narrowed data
        return recursiveBinarySearch(arr, mid + 1, lastElement, elementToSearch);
    }

    return -1;
}

La diferencia en el enfoque recursivo es que invocamos el método mismo una vez que obtenemos la nueva partición. En el enfoque iterativo, cada vez que determinamos la nueva partición, modificamos el primer y el último elemento y repetimos el proceso en el mismo ciclo.

Otra diferencia aquí es que las llamadas recursivas se insertan en la pila de llamadas del método y ocupan una unidad de espacio por llamada recursiva.

Podemos usar este algoritmo así:

1
2
int index = binarySearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 0, 10, 67);
print(67, index);

Producción:

1
67 found at index: 5

Complejidad del tiempo

Dado que Binary Search divide la matriz a la mitad cada vez que su complejidad de tiempo es O(log(N)). Esta complejidad de tiempo es una mejora notable en la complejidad de tiempo O(N) de la búsqueda lineal.

Complejidad espacial

Esta búsqueda requiere solo una unidad de espacio para almacenar el elemento a buscar. Por lo tanto, su complejidad espacial es O(1).

Si la búsqueda binaria se implementa de forma recursiva, debe almacenar la llamada al método en una pila. Esto puede requerir espacio O(log(N)) en el peor de los casos.

Aplicaciones

Es el algoritmo de búsqueda más utilizado en la mayoría de las bibliotecas para realizar búsquedas. El árbol de búsqueda binaria también es utilizado por muchas estructuras de datos que almacenan datos ordenados.

La búsqueda binaria también se implementa en las API de Java en el método Arrays.binarySearch.

Búsqueda de patrones de Knuth Morris Pratt

Como su nombre lo indica, es un algoritmo para encontrar un patrón en el texto dado. Este algoritmo fue desarrollado por Donald Knuth, Vaughan Pratt y James Morris, de ahí el nombre.

Explicación

En esta búsqueda, el patrón dado se compila primero. Al compilarlo, tratamos de encontrar el prefijo y el sufijo de la cadena de patrón. Esto nos ayuda cuando ocurre una falta de coincidencia: no comenzaremos a buscar la siguiente coincidencia desde el comienzo del índice.

En cambio, omitimos la parte de la cadena de texto que ya hemos comparado y comenzamos a comparar más allá de esa parte. Determinamos esta parte conociendo el prefijo y el sufijo para estar seguros de qué parte ya se comparó y se puede omitir de manera segura.

Como resultado de esta omisión, podemos ahorrar muchas comparaciones y KMP funciona más rápido que un algoritmo de fuerza bruta ingenuo.

Implementación

Vamos a crear el método compilePatternArray(), que será utilizado más tarde por el algoritmo de búsqueda KMP:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static int[] compilePatternArray(String pattern) {
    int patternLength = pattern.length();
    int len = 0;
    int i = 1;
    int[] compliedPatternArray = new int[patternLength];
    compliedPatternArray[0] = 0;

    while (i < patternLength) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            compliedPatternArray[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = compliedPatternArray[len - 1];
            } else {
                compliedPatternArray[i] = len;
                i++;
            }
        }
    }
    System.out.println("Compiled Pattern Array " + Arrays.toString(compliedPatternArray));
    return compliedPatternArray;
}

La matriz de patrones compilada se puede considerar como una matriz que almacena el patrón de caracteres en la matriz de patrones. El objetivo principal detrás de la creación de esta matriz es encontrar el prefijo y el sufijo en el patrón. Si conocemos estos elementos en el patrón, podemos evitar la comparación desde el comienzo del texto y simplemente comparar el siguiente carácter después de que haya ocurrido la falta de coincidencia.

La matriz compilada almacena la posición de índice de la aparición anterior del carácter actual en la matriz de patrones.

Implementemos el algoritmo en sí:

 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
public static List<Integer> performKMPSearch(String text, String pattern) {
    int[] compliedPatternArray = compilePatternArray(pattern);

    int textIndex = 0;
    int patternIndex = 0;

    List<Integer> foundIndexes = new ArrayList<>();

    while (textIndex < text.length()) {
        if (pattern.charAt(patternIndex) == text.charAt(textIndex)) {
            patternIndex++;
            textIndex++;
        }
        if (patternIndex == pattern.length()) {
            foundIndexes.add(textIndex - patternIndex);
            patternIndex = compliedPatternArray[patternIndex - 1];
        }

        else if (textIndex < text.length() && pattern.charAt(patternIndex) != text.charAt(textIndex)) {
            if (patternIndex != 0)
                patternIndex = compliedPatternArray[patternIndex - 1];
            else
                textIndex = textIndex + 1;
        }
    }
    return foundIndexes;
}

Aquí comenzamos comparando secuencialmente los caracteres en el patrón y la matriz de texto. Seguimos avanzando hasta que seguimos obteniendo una coincidencia de patrones y matrices de texto. De esta forma, si llegamos al final de la matriz de patrones mientras lo emparejamos, significa que hemos encontrado una ocurrencia del patrón en el texto.

Sin embargo, si encontramos una discrepancia al comparar las dos matrices, movemos el índice de la matriz de caracteres del patrón al valor en compiledPatternArray() y también pasamos al siguiente carácter en la matriz de texto. Aquí es donde la búsqueda KMP supera al enfoque de fuerza bruta, ya que no compara los caracteres de texto más de una vez si no coinciden.

Intentemos ejecutar el algoritmo:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
String pattern = "AAABAAA";
String text = "ASBNSAAAAAABAAAAABAAAAAGAHUHDJKDDKSHAAJF";

List<Integer> foundIndexes = KnuthMorrisPrathPatternSearch.performKMPSearch(text, pattern);

if (foundIndexes.isEmpty()) {
    System.out.println("Pattern not found in the given text String");
} else {
    System.out.println("Pattern found in the given text String at positions: " + .stream().map(Object::toString).collect(Collectors.joining(", ")));
}

En el texto del patrón AAABAAA, se observa el siguiente patrón y se codifica en la matriz de patrones:

  • El patrón A (Single A) se repite en el índice 1 y nuevamente en el 4.
  • El patrón AA (Doble A) se repite en el índice 2 y nuevamente en el índice 5.
  • El patrón AAA (3 A's) se repite en el índice 6.

Veamos el resultado para validar nuestra discusión hasta ahora:

1
2
Compiled Pattern Array [0, 1, 2, 0, 1, 2, 3]
Pattern found in the given text String at positions: 8, 14

El patrón que describimos se nos muestra claramente en la matriz de patrones cumplida en la salida.

Con la ayuda de esta matriz compilada, el algoritmo de búsqueda de KMP puede buscar el patrón dado en el texto sin retroceder en la matriz de texto.

Complejidad del tiempo

Este algoritmo necesita comparar todos los elementos en el texto dado para encontrar el patrón. El tiempo requerido para eso es O(N) . Para compilar la cadena del patrón, necesitamos visitar cada uno de los caracteres del patrón y esa es otra iteración O(M).

Entonces, el tiempo total que toma este algoritmo será O(M+N).

Complejidad espacial

Necesitamos espacio O(M) para almacenar el patrón compilado para un patrón dado de tamaño M

Aplicaciones

Este algoritmo se emplea particularmente en herramientas de texto para encontrar patrones en archivos de texto.

Saltar búsqueda

Explicación

Esta búsqueda es similar a la búsqueda binaria, pero en lugar de saltar tanto hacia adelante como hacia atrás, solo saltaremos hacia adelante. Tenga en cuenta que Jump Search también requiere que se ordene la colección.

En Jump Search, saltamos en el intervalo sqrt(arraylength) hasta llegar a un elemento mayor que el elemento actual o el final de la matriz. En cada salto, se registra el paso anterior.

Si nos encontramos con un elemento mayor que el elemento que estamos buscando, dejamos de saltar. Luego, ejecutamos una búsqueda lineal entre el paso anterior y el paso actual.

Esto hace que el espacio de búsqueda sea mucho más pequeño para la búsqueda lineal y, por lo tanto, se convierte en una opción viable.

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int jumpSearch(int[] integers, int elementToSearch) {

    int arrayLength = integers.length;
    int jumpStep = (int) Math.sqrt(integers.length);
    int previousStep = 0;

    while (integers[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) {
        previousStep = jumpStep;
        jumpStep += (int)(Math.sqrt(arrayLength));
        if (previousStep >= arrayLength)
            return -1;
    }
    while (integers[previousStep] < elementToSearch) {
        previousStep++;
        if (previousStep == Math.min(jumpStep, arrayLength))
            return -1;
    }

    if (integers[previousStep] == elementToSearch)
        return previousStep;
    return -1;
}

Comenzamos con el jumpstep de tamaño raíz cuadrada de la longitud de la matriz y seguimos saltando hacia adelante con este mismo tamaño hasta que encontremos un elemento que sea igual o mayor que el elemento que estamos buscando.

Así que primero visitamos el elemento en integers[jumpStep], luego integers[2jumpStep], integers[3jumpStep] y así sucesivamente. También almacenamos el elemento anterior visitado en la variable previousStep.

Una vez que encontramos un valor tal que enteros[pasoanterior] < elementoParaBuscar < enteros[paso de salto], realizamos una búsqueda lineal entre enteros[pasoanterior] y enteros[paso de salto] o un elemento mayor que elementToSearch.

Podemos usar el algoritmo así:

1
2
int index = jumpSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

Producción:

1
67 found at Index 5

Complejidad del tiempo

Dado que saltamos pasos sqrt(arraylength) en cada iteración, la complejidad de tiempo para esta búsqueda es O(sqrt(N)).

Complejidad espacial

La complejidad del espacio para esta búsqueda es O(1) ya que requiere solo una unidad de espacio para almacenar el elemento a buscar.

Solicitud

Esta búsqueda se utiliza sobre la búsqueda binaria cuando es costoso volver atrás. Esta restricción se enfrenta cuando usamos un medio giratorio como unidades cuando buscar hacia adelante es fácil, pero saltar en la dirección cambiada varias veces es costoso.

Búsqueda de interpolación

Explicación

Búsqueda de interpolación se utiliza para buscar elementos en una matriz ordenada. Esta búsqueda es particularmente útil si sabemos que los datos en la estructura subyacente están distribuidos uniformemente.

Si los datos se distribuyen uniformemente, adivinar la ubicación de un elemento puede ser más preciso, a diferencia de la búsqueda binaria, donde siempre tratamos de encontrar el elemento en el medio de la matriz.

La búsqueda de interpolación utiliza fórmulas de interpolación para encontrar el lugar más probable donde se puede encontrar el elemento en la matriz. Sin embargo, para que estas fórmulas sean efectivas, la matriz de búsqueda debe ser grande; de ​​lo contrario, funciona como la búsqueda lineal:

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int interpolationSearch(int[] integers, int elementToSearch) {

    int startIndex = 0;
    int lastIndex = (integers.length - 1);

    while ((startIndex <= lastIndex) && (elementToSearch >= integers[startIndex]) &&
           (elementToSearch <= integers[lastIndex])) {
        // using interpolation formulae to find the best probable position for this element to exist
        int pos = startIndex + (((lastIndex-startIndex) /
          (integers[lastIndex]-integers[startIndex]))*
                        (elementToSearch - integers[startIndex]));

        if (integers[pos] == elementToSearch)
            return pos;

        if (integers[pos] < elementToSearch)
            startIndex = pos + 1;

        else
            lastIndex = pos - 1;
    }
    return -1;
}

Podemos usar este algoritmo así:

1
2
int index = interpolationSearch(new int[]{1,2,3,4,5,6,7,8}, 6);
print(67, index);

Producción:

1
6 found at Index 5

Echemos un vistazo a cómo las fórmulas de interpolación hacen su magia para buscar 6:

1
2
3
4
5
startIndex = 0
lastIndex = 7
integers[lastIndex] = 8
integers[startIndex] = 1
elementToSearch = 6

Ahora apliquemos estos valores a las fórmulas para estimar el índice del elemento de búsqueda:

$$
índice = 0 + (7-0)/(8-1)*(6-1) = 5
$$

El elemento en integers[5] es 6, que es el elemento que buscábamos. Como podemos ver aquí, el índice del elemento se calcula en un solo paso ya que los datos se distribuyen uniformemente.

Complejidad del tiempo

La complejidad de tiempo del mejor caso para este algoritmo es O(log log N) pero en el peor de los casos, es decir, cuando los elementos no están distribuidos uniformemente, es comparable a la complejidad de tiempo de búsqueda lineal que es O(N).

Complejidad espacial

Este algoritmo también requiere solo una unidad de espacio para almacenar el elemento a buscar. Por lo tanto, su complejidad espacial es O(1).

Solicitud

Esta búsqueda es útil cuando los datos se distribuyen uniformemente como números de teléfono en un directorio.

Búsqueda exponencial

Explicación

Búsqueda exponencial se utiliza para buscar elementos saltando en posiciones exponenciales, es decir, en potencias de 2.

En esta búsqueda, básicamente estamos tratando de encontrar un rango comparativamente más pequeño en el que podamos buscar el elemento utilizando otros algoritmos de búsqueda acotados como la búsqueda binaria.

No hace falta decir que la colección debe ordenarse para que esto funcione.

Implementación

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public static int exponentialSearch(int[] integers, int elementToSearch) {

    if (integers[0] == elementToSearch)
        return 0;
    if (integers[integers.length - 1] == elementToSearch)
        return integers.length;

    int range = 1;

    while (range < integers.length && integers[range] <= elementToSearch) {
        range = range * 2;
    }

    return Arrays.binarySearch(integers, range / 2, Math.min(range, integers.length), elementToSearch);
}

Podemos usar este algoritmo así:

1
2
int index = exponentialSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

Así es como funciona el algoritmo:

Intentamos encontrar un elemento que sea mayor que el elemento que estamos buscando. Hacemos esto para minimizar el rango de elementos que estamos buscando. Aumentamos el rango multiplicándolo por 2 y verificamos nuevamente si llegamos a un elemento mayor que el elemento que estamos buscando o al final de la matriz. Una vez que se logra cualquiera de esto, salimos del bucle. Luego realizamos una búsqueda binaria con startIndex como range/2 y lastIndex como range.

En nuestro caso, este valor de rango se logra en 8 y el elemento en enteros[8] es 95. Entonces, el rango donde realizamos la búsqueda binaria es:

1
2
3
startIndex = range/2 = 4

lastIndex = range = 8

Con esto la llamada de búsqueda binaria se convierte en:

1
Arrays.binarySearch(integers, 4, 8, 6);

Producción:

1
67 found at Index 5

Una cosa importante a tener en cuenta aquí es que podemos acelerar la multiplicación por 2 usando el operador de desplazamiento a la izquierda rango << 1 en lugar del operador *.

Complejidad del tiempo

La complejidad de tiempo en el peor de los casos para este tipo de búsqueda es O(log(N)).

Complejidad espacial

Este algoritmo requiere espacio O(1) para almacenar el elemento que se busca si el algoritmo de búsqueda binaria subyacente es iterativo.

Si el algoritmo de búsqueda binaria subyacente es recursivo, la complejidad del espacio se convierte en O(log(N)).

Aplicaciones

La búsqueda exponencial se usa cuando tenemos una matriz enorme o ilimitada. La aplicación de la búsqueda binaria en todo el conjunto de datos puede resultar costosa. La búsqueda exponencial puede reducir estos datos en particiones más pequeñas y fáciles de buscar.

Búsqueda de Fibonacci {#búsqueda de Fibonacci}

Explicación

La búsqueda de Fibonacci emplea el enfoque divide y vencerás en el que dividimos elementos de manera desigual según la serie de Fibonacci. Esta búsqueda requiere que la matriz esté ordenada.

A diferencia de la búsqueda binaria, donde dividimos los elementos en mitades iguales para reducir el rango de la matriz, en la búsqueda de Fibonacci intentamos usar la suma o la resta para obtener un rango más pequeño.

Recuerda que la fórmula de la serie de Fibonacci es:

$$
fibo(n) = fibo(n-1)+fibo(n-2)
$$

Los dos primeros números de esta serie son Fibo(0) = 0 y Fibo(1) = 1. Entonces, según esta fórmula, la serie se ve así 0, 1, 1, 2, 3, 5, 8, 13, 21... Las observaciones interesantes a tener en cuenta aquí son las siguientes:

Fibo(N-2) es aproximadamente 1/3 de Fibo(N)

Fibo(N-1) es aproximadamente 2/3 de Fibo(N)

Entonces, cuando usamos los números de la serie de Fibonacci para dividir el rango, se divide en la misma proporción que arriba.

Implementación

Echemos un vistazo a la implementación para tener una idea más clara:

 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
public static int fibonacciSearch(int[] integers, int elementToSearch) {

    int fibonacciMinus2 = 0;
    int fibonacciMinus1 = 1;
    int fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
    int arrayLength = integers.length;

    while (fibonacciNumber < arrayLength) {
        fibonacciMinus2 = fibonacciMinus1;
        fibonacciMinus1 = fibonacciNumber;
        fibonacciNumber = fibonacciMinus2 + fibonacciMinus1;
    }

    int offset = -1;

    while (fibonacciNumber > 1) {
        int i = Math.min(offset+fibonacciMinus2, arrayLength-1);

        if (integers[i] < elementToSearch) {
            fibonacciNumber = fibonacciMinus1;
            fibonacciMinus1 = fibonacciMinus2;
            fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
            offset = i;
        }

        else if (integers[i] > elementToSearch) {
            fibonacciNumber = fibonacciMinus2;
            fibonacciMinus1 = fibonacciMinus1 - fibonacciMinus2;
            fibonacciMinus2 = fibonacciNumber - fibonacciMinus1;
        }

        else return i;
    }

    if (fibonacciMinus1 == 1 && integers[offset+1] == elementToSearch)
        return offset+1;

    return -1;
}

Podemos ejecutar este algoritmo así:

1
2
int index = fibonacciSearch(new int[]{3, 22, 27, 47, 57, 67, 89, 91, 95, 99}, 67);
print(67, index);

Así es como funciona el algoritmo:

Comienza por encontrar primero el número en la serie de Fibonacci más cercano pero mayor que la longitud de la matriz. Esto sucede cuando fibonacciNumber está en 13, que es solo más que la longitud de la matriz: 10.

A continuación, comparamos los elementos de la matriz y, sobre la base de esa comparación, tomamos una de las siguientes acciones:

  • Compare el elemento a buscar con el elemento en fibonacciMinus2 y devuelva el índice si el valor coincide.
  • Si elementToSearch es mayor que el elemento actual, retrocedemos un paso en la serie de fibonacci y cambiamos los valores de fibonacciNumber, fibonacciMinus1 y fibonacciMinus2 en consecuencia. El desplazamiento se restablece al índice actual.
  • Si elementToSearch es más pequeño que el elemento actual, retrocedemos dos pasos en la serie de fibonacci y cambiamos los valores de fibonacciNumber, fibonacciMinus1 y fibonacciMinus2 en consecuencia.

Producción:

1
67 found at Index 5

Complejidad del tiempo

La complejidad temporal en el peor de los casos para esta búsqueda es O(log(N)).

Complejidad espacial

Si bien necesitamos guardar los tres números en la serie de Fibonacci y el elemento a buscar, necesitamos cuatro unidades adicionales de espacio.

Este requisito de espacio no aumenta con el tamaño de la matriz de entrada. Por lo tanto, podemos decir que la complejidad del espacio para la búsqueda de Fibonacci es O(1).

Aplicaciones

Esta búsqueda se utiliza cuando la división es una operación costosa para la CPU. Los algoritmos como la búsqueda binaria tienden a funcionar mal, ya que usan la división para dividir la matriz.

Otro beneficio de esta búsqueda es cuando los elementos de la matriz de entrada no caben en la RAM. En tales situaciones, un ámbito de operación localizado que realiza este algoritmo lo ayuda a ejecutarse mucho más rápido.

API de colecciones de Java

Ahora que hemos visto la implementación de múltiples algoritmos en Java, echemos un breve vistazo a la forma en que se realiza la búsqueda en diferentes colecciones de Java.

Matrices

Las matrices en Java se pueden buscar usando uno de los métodos java.util.BinarySearch. La búsqueda binaria en la versión Abrir JDK utiliza la forma iterativa de la búsqueda.

Echemos un vistazo rápido a cómo podemos usar este método:

1
2
3
4
5
int[] integers = {3, 22, 27, 47, 57, 67, 89, 91, 95, 99};

int elementToSearch = 67;

int index = java.util.Arrays.binarySearch(integers, elementToSearch);

Producción:

1
67 found at Index 5

La interfaz de lista

La interfaz de lista tiene principalmente dos métodos que se pueden usar para buscar: indexOf() y contains().

El método indexOf() devuelve el índice del elemento si existe en la lista o -1 si no existe.

El método contains() devuelve verdadero o falso dependiendo de la existencia del elemento. Llama internamente al método indexOf().

The Interfaz de lista uses Sequential Search to perform the index lookup and hence its time complexity is O(N).

Probemos una operación de búsqueda en una Lista:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
java.util.List<Integer> integers = new java.util.ArrayList<>();
integers.add(3);
integers.add(22);
integers.add(27);
integers.add(47);
integers.add(57);
integers.add(67);
integers.add(89);
integers.add(91);
integers.add(95);
integers.add(99);

int elementToSearch = 67;

int index = integers.indexOf(elementToSearch);

Producción:

1
67 found at Index 5

De manera similar, si no estamos interesados ​​en el índice pero solo queremos saber si el elemento existe en la Lista o no, podemos usar el método contains():

1
integers.contains(67)

Producción:

1
true

La interfaz del mapa

El mapa es una estructura de datos de pares clave-valor. La interfaz Map en Java utiliza la búsqueda HashBased así como el Binary Search Tree.

La clase java.util.HashMap usa un valor hash de la clave para almacenar los elementos en el Mapa. Recuperar el elemento del Mapa usando las teclas correctas para hash y un buen algoritmo Hashing (de modo que no ocurran colisiones) es O(1).

Otra implementación de la interfaz Map es java.util.TreeMap, que internamente usa Árbol rojo-negro que es un tipo de árbol de búsqueda binaria autoequilibrado. Los elementos agregados a este árbol se almacenan automáticamente en la forma ordenada por el árbol.

La complejidad temporal de la búsqueda en un árbol binario es O(log(N)).

Veamos cómo podemos buscar un elemento en un Mapa:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
java.util.Map<Integer, String> integers = new java.util.HashMap<>();
integers.put(3,"three");
integers.put(22,"twentytwo");
integers.put(27,"twentyseven");
integers.put(47,"fortyseven");
integers.put(57,"fiftyseven");
integers.put(67,"sixtyseven");
integers.put(89,"eightynine");
integers.put(91,"ninetyone");
integers.put(95,"ninetyfive");
integers.put(99,"ninetynine");

String value = integers.get(67);

System.out.println("the value at key 67 is: " + value);

Hemos creado un mapa con una clave como un Entero y el valor como ese Entero en palabras. Luego buscamos una clave y obtenemos el número entero como palabras en la salida.

Una cosa importante a tener en cuenta aquí es que el mapa no almacenará claves duplicadas. Si intentamos insertar un valor duplicado, sobrescribirá la clave y el valor existentes con el nuevo.

Producción:

1
the value at key 67 is: sixtyseven

La interfaz Map también contiene el método containsKey() que se puede usar para determinar si una clave determinada existe o no:

1
integers.containsKey(67);

La interfaz del conjunto

La estructura de datos Set se utiliza para almacenar elementos únicos. La interfaz Establecer es esencialmente un contenedor sobre la interfaz ‘Mapa’ descrita anteriormente que almacena elementos en la Clave del ‘Mapa’.

Al igual que con la interfaz Map, utiliza la búsqueda Binary y Hash-based.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
java.util.Set<Integer> integers = new java.util.HashSet<>();
integers.add(3);
integers.add(22);
integers.add(27);
integers.add(47);
integers.add(57);
integers.add(67);
integers.add(89);
integers.add(91);
integers.add(95);
integers.add(99);

int elementToSearch = 67;

boolean isNumberExists = integers.contains(elementToSearch);

if (isNumberExists)
    System.out.println(elementToSearch + " exists in the set");
else
    System.out.println(elementToSearch + " does not exist in the set");

No hay índice en la interfaz Set y, como tal, la operación de búsqueda contains() devuelve verdadero o falso dependiendo de la existencia del elemento que se busca.

En este caso, dado que el elemento existe en el conjunto, obtenemos el siguiente resultado:

1
67 exists in the set

Comparación de tiempo del algoritmo de búsqueda

Dicho esto, a menudo es útil ejecutar todos estos algoritmos varias veces para tener una idea de cómo funcionan.

Busquemos el elemento 573400 en una matriz ordenada que está poblada con un millón de enteros.

Estos son los resultados de los algoritmos:


tiempo(ns) Lineal Binario (Iterativo) Binario (Recursivo) Salto Interpolación Exponencial Fibonacci Primera ejecución 5 229 901 23 014 14 928 125 647 18 661 49 762 13 373 Segunda ejecución 8 436 389 24 570 14 306 329 046 18 349 206 820 21 770 Tercera carrera 7 207 909 24 569 23 326 585 005 19 593 106 054 23 325 Cuarta Ejecución 5 888 615 33 589 27 057 218 327 23 015 111 341 25 813 Quinta ejecución 3 002 466 20 216 46 962 132 800 15 861 65 311 20 216 Sexta ejecución 6 896 901 12 440 26 124 212 107 7 465 106 054 38 254 Séptima carrera 6 916 495 59 714 13 373 210 241 15 240 126 891 13 684 Ocho Carrera 6 781 828 22 393 46 962 159 235 10 575 83 972 26 436 Novena Ejecución 6 917 116 11 507 18 660 265 911 28 302 130 002 12 751 Décima Carrera 3 811 085 41 053 89 259 302 922 26 436 183 184 25 192


Es fácil ver que la búsqueda lineal toma significativamente más tiempo que cualquier otro algoritmo para buscar este elemento, ya que evaluó todos y cada uno de los elementos antes del que estamos buscando. Si estuviéramos buscando el primer elemento, la búsqueda lineal sería la más eficiente aquí.

También es fácil ver que la búsqueda binaria, de interpolación y de Fibonacci muestra los mejores resultados para esta matriz en particular.

Conclusión

Cada sistema tiene su propio conjunto único de restricciones y requisitos. Un algoritmo de búsqueda utilizado correctamente, basado en esas restricciones, puede contribuir en gran medida a determinar el rendimiento del sistema.

En este artículo, echamos un vistazo a cómo funcionan los diferentes algoritmos de búsqueda y en qué circunstancias encajan perfectamente. También vimos cómo Java usa diferentes algoritmos de búsqueda en su API de colecciones integrada.

Como siempre, puedes encontrar el código fuente de los algoritmos descritos en este artículo aquí.