Algoritmos de búsqueda en Java

A

Introducción

La búsqueda es una de las acciones más comunes que se realizan en las aplicaciones comerciales habituales. Esto implica ir a buscar algunos datos almacenados en estructuras de datos como Arrays, List, Map, etc. Más a menudo que no, 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 utilizar para adaptarse a diferentes escenarios. También los implementaremos en Java y analizaremos su rendimiento con algunos parámetros conocidos como Time and Space Complexity.

  • Búsqueda lineal
  • Búsqueda binaria
  • Búsqueda de patrones de Knuth Morris Pratt
  • Saltar búsqueda
  • Búsqueda de interpolación
  • Búsqueda exponencial
  • Búsqueda de Fibonacci
  • API de colecciones de Java

Búsqueda lineal

La búsqueda lineal o secuencial es el algoritmo de búsqueda más simple. 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 raramente se utiliza en producción y, en la mayoría de los casos, otros algoritmos lo superan.

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 llega al final de la estructura.

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

Implementación

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

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:

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:

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);
    }
}

Salida:

67 found at index: 8

Complejidad del tiempo

Aquí estamos iterando a través de todo el conjunto de Nelementos 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, iteraremos Nveces antes de encontrar el elemento.

Por 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 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 sin clasificar 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

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

Explicación

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

Divide la colección de entrada en mitades iguales y con cada iteración compara el elemento objetivo con el elemento del 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 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 del tiempo y el espacio entre estas dos implementaciones, aunque esto no es válido para todos los lenguajes.

Implementación

Iterativo

Primero echemos un vistazo al enfoque iterativo :

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í:

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

Salida:

67 found at index: 5

Recursivo

Y ahora echemos un vistazo a la implementación recursiva:

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 en sí una vez que obtenemos la nueva partición. En el enfoque iterativo, siempre que determinamos la nueva partición, modificamos el primer y ú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í:

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

Salida:

67 found at index: 5

Complejidad del tiempo

Dado que la búsqueda binaria divide la matriz en 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 tanto, su complejidad espacial es O (1).

Si la búsqueda binaria se implementa de forma recursiva, necesita almacenar la llamada al método en una pila. Esto puede requerir un 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 lo utilizan muchas estructuras de datos que almacenan datos ordenados.

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

Búsqueda de patrones de Knuth Morris Pratt

Como su nombre 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, primero se compila el patrón dado. Al compilarlo, intentamos 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 principio 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 está comparada y se puede omitir con seguridad.

Como resultado de este salto, podemos guardar muchas comparaciones y KMP funciona más rápido que un algoritmo de fuerza bruta ingenuo.

Implementación

Creemos el compilePatternArray()método, que luego será utilizado por el algoritmo de búsqueda de KMP:

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 comparar desde el principio 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 del índice de la ocurrencia anterior del carácter actual en la matriz de patrones.

Implementemos el algoritmo en sí:

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 los caracteres en el patrón y la matriz de texto secuencialmente. Seguimos avanzando hasta que obtengamos una coincidencia de patrones y matrices de texto. De esta manera, si llegamos al final de la matriz de patrones mientras coincidimos, significa que hemos encontrado una ocurrencia del patrón en el texto.

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

Intentemos ejecutar el algoritmo:

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, el siguiente patrón se observa y 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) se repite en el índice 6.

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

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 cumplidos en la salida.

Con la ayuda de esta matriz compilada, el algoritmo de búsqueda 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 en el patrón y eso son otras iteraciones 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 de tamaño dado 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 hacia adelante y 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)adelante hasta llegar a un elemento mayor que el elemento actual o al 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

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 jumpsteptamaño de la raíz cuadrada de la longitud de la matriz y seguimos saltando hacia adelante con este mismo tamaño hasta que encontramos un elemento que es 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 previousStepvariable.

Una vez que encontramos un valor tal que integers[previousStep]< elementToSearch< integers[jumpStep], se realiza una búsqueda lineal entre integers[previousStep]y integers[jumpStep]o un elemento de mayor elementToSearch.

Podemos usar el algoritmo así:

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

Salida:

67 found at Index 5

Complejidad del tiempo

Dado que saltamos sqrt(arraylength)pasos 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 solo requiere una unidad de espacio para almacenar el elemento que se busca.

Solicitud

Esta búsqueda se utiliza sobre la búsqueda binaria cuando saltar hacia atrás es costoso. Esta restricción se enfrenta cuando usamos medios giratorios 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

La búsqueda por 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, en la que siempre intentamos encontrar el elemento en el medio de la matriz.

La búsqueda de interpolación utiliza fórmulas de interpolación para encontrar el mejor lugar 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 una búsqueda lineal:

Implementación

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í:

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

Salida:

6 found at Index 5

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

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 estábamos buscando. Como podemos ver aquí, el índice del elemento se calcula en un solo paso, ya que los datos se distribuyen uniformemente.

Complejidad del tiempo

El mejor caso de complejidad de tiempo 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 que se buscará. Por 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

La 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 limitada como la búsqueda binaria.

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

Implementación

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í:

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 la gama de elementos que estamos buscando. Aumentamos el rango multiplicándolo por 2 y comprobamos 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 estos, salimos del ciclo. Luego realizamos una búsqueda binaria con startIndexas range/2y lastIndexas range.

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

startIndex = range/2 = 4

lastIndex = range = 8

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

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

Salida:

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 en range << 1lugar 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 a particiones más pequeñas y fáciles de buscar.

Búsqueda de Fibonacci

Explicación

La búsqueda de Fibonacci emplea un enfoque de dividir y conquistar en el que dividimos el elemento de manera desigual según la serie de Fibonacci. Esta búsqueda requiere que se ordene la matriz.

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.

Recuerde que la fórmula para la serie de Fibonacci es:

$$
Fibonacci (N) = Fibonacci (N-1) + Fibonacci (N-2)
$$

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

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

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

Entonces, cuando usamos números de 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:

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í:

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 encontrando primero el número en la serie de Fibonacci más cercano pero mayor que la longitud de la matriz. Esto sucede cuando fibonacciNumberestá en 13, que es un poco 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 que se buscará con el elemento en fibonacciMinus2y devuelva el índice si el valor coincide.
  • Si elementToSearches mayor que el elemento actual, retrocedemos un paso en la serie de fibonacci y cambiamos los valores de fibonacciNumber, fibonacciMinus1& en fibonacciMinus2consecuencia. La compensación se restablece al índice actual.
  • Si el elementToSearches menor que el elemento actual, nos movemos dos pasos hacia atrás en la serie de Fibonacci y cambiar los valores de fibonacciNumber, fibonacciMinus1y fibonacciMinus2en consecuencia.

Salida:

67 found at Index 5

Complejidad del tiempo

La complejidad de tiempo 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 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 tener malos resultados, ya que utilizan la división para dividir la matriz.

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

API de colecciones de Java

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

Matrices

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

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

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

int elementToSearch = 67;

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

Salida:

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 indexOf()método devuelve el índice del elemento si existe en la lista o -1si no existe.

El contains()método retorna trueo falsedepende de la existencia del elemento. Internamente llama al indexOf()método.

La interfaz de lista utiliza la búsqueda secuencial para realizar la búsqueda de índice y, por lo tanto, su complejidad de tiempo es O(N).

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

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);

Salida:

67 found at Index 5

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

integers.contains(67)

Salida:

true

La interfaz del mapa

El mapa es una estructura de datos de pares clave-valor. La Mapinterfaz en Java utiliza HashBasedbúsquedas y Binary Search Tree.

La java.util.HashMapclase usa un valor hash de keypara almacenar los elementos en el mapa. Recuperar el elemento del mapa usando las claves correctas para hash y un buen algoritmo de hash (tal que no ocurran colisiones) sí lo es O(1).

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

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

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

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 Integer y el valor como Integer en palabras. Luego buscamos una clave y obtenemos el 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.

Salida:

the value at key 67 is: sixtyseven

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

integers.containsKey(67);

La interfaz de conjunto

La Setestructura de datos se utiliza para almacenar elementos únicos. La interfaz Set es esencialmente una envoltura sobre la Mapinterfaz descrita anteriormente que almacena elementos en la clave del Map.

Al igual que con la Mapinterfaz, utiliza Binaryy Hash-basedsearch.

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 Setinterfaz y, como tal, la operación de búsqueda contains()regresa trueo falsedepende de la existencia del elemento que se busca.

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

67 exists in the set

Comparación de tiempo de 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 573400en una matriz ordenada que se llena con un millón de enteros.

Estos son los resultados de los algoritmos:

tiempo (ns) LinearBinary (iterativo) Binario (recursivo) JumpInterpolationExponentialFibonacci

Primer intento5 229 90123 01414 928125 64718 66149 76213 373
Segunda ejecución8 436 38924 57014 306329 04618 349206 82021 770
Tercera carrera7 207 90924 56923 326585 00519 593106 05423 325
Cuarta carrera5 888 61533 58927 057218 32723 015111 34125 813
Quinta carrera3 002 46620 21646 962132 80015 86165 31120 216
Sexta carrera6 896 90112 44026 124212 1077 465106 05438 254
Séptima carrera6 916 49559 71413 373210 24115 240126 89113 684
Ocho correr6 781 82822 39346 962159 23510 57583 97226 436
Novena carrera6 917 11611 50718 660265 91128 302130 00212 751
Décima carrera3 811 08541 05389 259302 92226 436183 18425 192

Es fácil ver que la búsqueda lineal tarda mucho más que cualquier otro algoritmo en buscar este elemento, ya que evaluó todos y cada uno de los elementos antes que el 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 Binary, Interpolation y Fibonacci Search muestran 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, analizamos cómo funcionan los diferentes algoritmos de búsqueda y bajo qué circunstancias encajan perfectamente. También vimos cómo Java utiliza diferentes algoritmos de búsqueda en su API de colecciones incorporada.

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

 

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad