Algoritmos de búsqueda en Java

Introducción

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

Busqueda lineal

La búsqueda lineal o secuencial es el algoritmo de búsqueda más simple. Si bien es ciertamente 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 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 llega al final de la estructura.
Si se encuentra el elemento, generalmente devolvemos su posición en la estructura de datos. Si no, normalmente volvemos -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 sencillo método de ayuda 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 de forma secuencial para obtener la ubicación del elemento que se está buscando. El peor de los casos para este algoritmo será si el elemento que estamos buscando es el último elemento de la matriz.
En este caso, repetiremos los Ntiempos antes de encontrar el elemento.
Por lo tanto, la complejidad del tiempo 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 pequeño y sin clasificar de datos que garantiza que no aumentará mucho su 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 rápido tiempo de búsqueda.

Explicación

Este tipo de búsqueda utiliza la metodología Dividir y Conquistar 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 de objetivo con el elemento en el medio.
Si se encuentra el elemento, la búsqueda termina. Si no, seguimos 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 central.
Por eso es importante tener una colección ordenada para la búsqueda binaria.
La búsqueda finaliza cuando firstIndex(nuestro puntero) pasa lastIndex(último elemento), lo que implica que hemos buscado en toda la matriz y que 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 válido para todos los idiomas.

Implementación

Iterativo
Veamos primero el 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, cada vez que determinamos la nueva partición modificamos los elementos primero y último y repetimos el proceso en el mismo bucle.
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

Como Binary Search divide la matriz en la mitad cada vez que su complejidad de tiempo es O (log (N))Esta complejidad de tiempo es una mejora marcada 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 recursivamente, debe 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 la búsqueda. El árbol de búsqueda binaria es utilizado por muchas estructuras de datos, así como para almacenar 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 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, intentamos encontrar el prefijo y el sufijo de la cadena del patrón. Esto nos ayuda cuando ocurre una falta de coincidencia: no comenzaremos a buscar la próxima coincidencia desde el principio del índice.
En su lugar, 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 al conocer el prefijo y el sufijo, por lo que estamos seguros de qué parte ya se ha comparado y se puede omitir de forma segura.
Como resultado de este salto, podemos guardar muchas comparaciones y KMP realiza más rápido que un algoritmo de fuerza bruta ingenuo.

Implementación

Vamos a crear el compilePatternArray()método, que será utilizado más adelante por el algoritmo de búsqueda 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 la comparación desde el inicio 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 aparición anterior del carácter actual en la matriz del patrón.
Implementemos el algoritmo mismo:
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 de forma secuencial. Seguimos avanzando hasta que obtenemos una combinación de matrices de patrones y texto. De esta manera, si alcanzamos el final de la matriz del patrón mientras la comparamos, 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 compiledPatternArray()y también nos movemos al siguiente carácter en la matriz de texto. Aquí es donde la búsqueda de KMP supera el enfoque de fuerza bruta, ya que no compara los caracteres del texto más de una vez si hay una falta de coincidencia.
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 del patrón:
  • El patrón A(Single A) se repite en el índice 1 y nuevamente en 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 el momento:
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 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 de patrones necesitamos visitar cada uno de los caracteres en el patrón y esa es otra iteración de O (M) .
Entonces, el tiempo total que tomará 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 dadoM

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 la colección se ordene.
En la búsqueda por salto, saltamos en el intervalo sqrt(arraylength)hacia adelante hasta que alcanzamos 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

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 la jumpstepraíz cuadrada de tamaño de la longitud de la matriz y seguimos avanzando 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 element 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]elementToSearchintegers[jumpStep], se realiza una búsqueda lineal entre integers[previousStep]integers[jumpStep]o un elemento mayor que 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 del 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 a buscar.

Solicitud

Esta búsqueda se usa sobre la búsqueda binaria cuando el salto hacia atrás es costoso. Esta restricción se enfrenta cuando utilizamos medios giratorios como unidades de disco cuando buscar hacia delante es fácil, pero saltar en la dirección cambiada varias veces es costoso.

Búsqueda de interpolación

Explicación

La 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 se distribuyen uniformemente.
Si los datos se distribuyen uniformemente, hacer una estimación de la ubicación de un elemento puede ser más preciso, a diferencia de la búsqueda binaria, donde siempre intentamos encontrar el elemento en el centro de la matriz.
La búsqueda de interpolación usa 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 se realiza como 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  
Veamos cómo las fórmulas de interpolación hacen su magia 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:
yonorteremiX=0+(7-0)/(8-1)(6-1)=5
El elemento en integers[5]6 es el elemento que buscábamos. Como podemos ver aquí, el índice para el elemento se calcula en un solo paso, ya que los datos se distribuyen uniformemente.

Complejidad del tiempo

La mejor complejidad de tiempo de caso para este algoritmo es O (registro log N), pero en el peor de los casos, es decir, cuando los elementos no están distribuidos uniformemente, es comparable a la complejidad del 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. De ahí que su complejidad de espacio sea 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.
Básicamente, en esta búsqueda 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. Incrementamos el rango al multiplicarlo por 2 y verificamos de nuevo si alcanzamos un elemento mayor que el elemento que estamos buscando o el final de la matriz. Una vez que se logra algo de esto, salimos del ciclo. Luego realizamos búsquedas binarias con startIndexcomo range/2lastIndexcomo range.
En nuestro caso, este valor de rango se alcanza en 8 y el elemento en integers[8]95. Por lo tanto, 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 en 2 utilizando el operador de cambio a la izquierda en range << 1lugar del *operador.

Complejidad del tiempo

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

Complejidad espacial

Este algoritmo requiere O (1) espacio para almacenar el elemento que se está buscando 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 utiliza 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 el 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 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 Fibonacci es:
Fyosegundoo(norte)=Fyosegundoo(norte-1)+Fyosegundoo(norte-2)
Los dos primeros números de esta serie son Fibo(0) = 0Fibo(1) = 1Entonces, de acuerdo con esta fórmula, la serie se ve así: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... Las observaciones interesantes para notar 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 los números de la serie de fibonacci para dividir el rango, se divide en la misma proporción que antes.

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 por encontrar primero el número en la serie de Fibonacci más cercano pero más largo que la longitud de la matriz. Esto ocurre cuando fibonacciNumberestá en 13, que es solo más que la longitud del arreglo - 10.
A continuación, comparamos los elementos de la matriz y, sobre la base de esa comparación, realizamos una de las siguientes acciones:
  • Compare el elemento a buscar con el elemento at 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 fibonacciNumberfibonacciMinus1y en fibonacciMinus2consecuencia. El desplazamiento se restablece al índice actual.
  • Si elementToSearches más pequeño que el elemento actual, retrocedemos dos pasos en la serie de fibonacci y cambiamos los valores de fibonacciNumberfibonacciMinus1y en fibonacciMinus2consecuencia.
Salida:
67 found at Index 5  

Complejidad del tiempo

El peor caso de complejidad de tiempo para esta búsqueda es O (log (N)) .

Complejidad espacial

Mientras que 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 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 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, veamos brevemente la forma en que se realiza la búsqueda en diferentes colecciones de Java.

Arrays

Los arreglos en Java se pueden buscar usando uno de los java.util.BinarySearchmétodos. La búsqueda binaria en la versión Open JDK usa 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 la lista

La interfaz de la lista tiene principalmente dos métodos que se pueden usar para buscar: indexOf()contains().
El indexOf()método devuelve el índice del elemento si existe en la lista o -1si no existe.
El contains()método devuelve truefalsedependiendo de la existencia del elemento. Llama internamente al indexOf()método.
La interfaz de la lista utiliza la búsqueda secuencial para realizar la búsqueda del índice y, por lo tanto, su complejidad de tiempo es O(N).
Probemos una operación de búsqueda en un 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 par clave-valor. La Mapinterfaz en Java utiliza tanto la HashBasedbúsqueda como la Binary Search Tree.
La java.util.HashMapclase utiliza un valor hash de keypara almacenar los elementos en el mapa. Recuperar el elemento del Mapa usando las teclas correctas para el hash y un buen algoritmo de Hashing (de modo que no se produzcan colisiones) es O(1).
Otra implementación de la interfaz del mapa es la java.util.TreeMap, que utiliza internamente el árbol rojo-negro, que es un tipo de árbol de búsqueda binaria con equilibrio automático. Los elementos agregados a este árbol se almacenan automáticamente de forma ordenada por el árbol.
La complejidad del tiempo de 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, se 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 usar para determinar si una clave dada 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 la búsqueda BinaryHash-based.
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 un índice en la Setinterfaz y, como tal, la operación de búsqueda contains()regresa truefalsedepende de la existencia del elemento que se está buscando.
En este caso, dado que el elemento existe en el conjunto, obtenemos la siguiente salida:
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 se desempeñan.
Busquemos el elemento 573400en una matriz ordenada que se llena con un millón de enteros.
Aquí están los resultados de los algoritmos:
tiempo (ns)LinealBinario (iterativo)Binario (Recursivo)SaltarInterpolaciónExponencialFibonacci
Primer intento5 229 90123 01414 928125 64718 66149 76213 373
Segunda carrera8 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 lleva mucho 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 hacer mucho para determinar el rendimiento del sistema.
En este artículo, analizamos cómo funcionan los diferentes algoritmos de búsqueda y en qué circunstancias se adaptan perfectamente. También vimos cómo Java utiliza diferentes algoritmos de búsqueda en su API de colecciones integrada.
Como siempre, puede encontrar el código fuente de los algoritmos descritos en este artículo aquí .

Introducción

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

Busqueda lineal

La búsqueda lineal o secuencial es el algoritmo de búsqueda más simple. Si bien es ciertamente 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 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 llega al final de la estructura.
Si se encuentra el elemento, generalmente devolvemos su posición en la estructura de datos. Si no, normalmente volvemos -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 sencillo método de ayuda 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 de forma secuencial para obtener la ubicación del elemento que se está buscando. El peor de los casos para este algoritmo será si el elemento que estamos buscando es el último elemento de la matriz.
En este caso, repetiremos los Ntiempos antes de encontrar el elemento.
Por lo tanto, la complejidad del tiempo 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 pequeño y sin clasificar de datos que garantiza que no aumentará mucho su 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 rápido tiempo de búsqueda.

Explicación

Este tipo de búsqueda utiliza la metodología Dividir y Conquistar 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 de objetivo con el elemento en el medio.
Si se encuentra el elemento, la búsqueda termina. Si no, seguimos 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 central.
Por eso es importante tener una colección ordenada para la búsqueda binaria.
La búsqueda finaliza cuando firstIndex(nuestro puntero) pasa lastIndex(último elemento), lo que implica que hemos buscado en toda la matriz y que 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 válido para todos los idiomas.

Implementación

Iterativo
Veamos primero el 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, cada vez que determinamos la nueva partición modificamos los elementos primero y último y repetimos el proceso en el mismo bucle.
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

Como Binary Search divide la matriz en la mitad cada vez que su complejidad de tiempo es O (log (N))Esta complejidad de tiempo es una mejora marcada 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 recursivamente, debe 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 la búsqueda. El árbol de búsqueda binaria es utilizado por muchas estructuras de datos, así como para almacenar 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 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, intentamos encontrar el prefijo y el sufijo de la cadena del patrón. Esto nos ayuda cuando ocurre una falta de coincidencia: no comenzaremos a buscar la próxima coincidencia desde el principio del índice.
En su lugar, 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 al conocer el prefijo y el sufijo, por lo que estamos seguros de qué parte ya se ha comparado y se puede omitir de forma segura.
Como resultado de este salto, podemos guardar muchas comparaciones y KMP realiza más rápido que un algoritmo de fuerza bruta ingenuo.

Implementación

Vamos a crear el compilePatternArray()método, que será utilizado más adelante por el algoritmo de búsqueda 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 la comparación desde el inicio 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 aparición anterior del carácter actual en la matriz del patrón.
Implementemos el algoritmo mismo:
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 de forma secuencial. Seguimos avanzando hasta que obtenemos una combinación de matrices de patrones y texto. De esta manera, si alcanzamos el final de la matriz del patrón mientras la comparamos, 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 compiledPatternArray()y también nos movemos al siguiente carácter en la matriz de texto. Aquí es donde la búsqueda de KMP supera el enfoque de fuerza bruta, ya que no compara los caracteres del texto más de una vez si hay una falta de coincidencia.
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 del patrón:
  • El patrón A(Single A) se repite en el índice 1 y nuevamente en 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 el momento:
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 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 de patrones necesitamos visitar cada uno de los caracteres en el patrón y esa es otra iteración de O (M) .
Entonces, el tiempo total que tomará 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 dadoM

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 la colección se ordene.
En la búsqueda por salto, saltamos en el intervalo sqrt(arraylength)hacia adelante hasta que alcanzamos 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

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 la jumpstepraíz cuadrada de tamaño de la longitud de la matriz y seguimos avanzando 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 element 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]elementToSearchintegers[jumpStep], se realiza una búsqueda lineal entre integers[previousStep]integers[jumpStep]o un elemento mayor que 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 del 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 a buscar.

Solicitud

Esta búsqueda se usa sobre la búsqueda binaria cuando el salto hacia atrás es costoso. Esta restricción se enfrenta cuando utilizamos medios giratorios como unidades de disco cuando buscar hacia delante es fácil, pero saltar en la dirección cambiada varias veces es costoso.

Búsqueda de interpolación

Explicación

La 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 se distribuyen uniformemente.
Si los datos se distribuyen uniformemente, hacer una estimación de la ubicación de un elemento puede ser más preciso, a diferencia de la búsqueda binaria, donde siempre intentamos encontrar el elemento en el centro de la matriz.
La búsqueda de interpolación usa 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 se realiza como 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  
Veamos cómo las fórmulas de interpolación hacen su magia 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:
yonorteremiX=0+(7-0)/(8-1)(6-1)=5
El elemento en integers[5]6 es el elemento que buscábamos. Como podemos ver aquí, el índice para el elemento se calcula en un solo paso, ya que los datos se distribuyen uniformemente.

Complejidad del tiempo

La mejor complejidad de tiempo de caso para este algoritmo es O (registro log N), pero en el peor de los casos, es decir, cuando los elementos no están distribuidos uniformemente, es comparable a la complejidad del 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. De ahí que su complejidad de espacio sea 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.
Básicamente, en esta búsqueda 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. Incrementamos el rango al multiplicarlo por 2 y verificamos de nuevo si alcanzamos un elemento mayor que el elemento que estamos buscando o el final de la matriz. Una vez que se logra algo de esto, salimos del ciclo. Luego realizamos búsquedas binarias con startIndexcomo range/2lastIndexcomo range.
En nuestro caso, este valor de rango se alcanza en 8 y el elemento en integers[8]95. Por lo tanto, 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 en 2 utilizando el operador de cambio a la izquierda en range << 1lugar del *operador.

Complejidad del tiempo

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

Complejidad espacial

Este algoritmo requiere O (1) espacio para almacenar el elemento que se está buscando 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 utiliza 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 el 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 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 Fibonacci es:
Fyosegundoo(norte)=Fyosegundoo(norte-1)+Fyosegundoo(norte-2)
Los dos primeros números de esta serie son Fibo(0) = 0Fibo(1) = 1Entonces, de acuerdo con esta fórmula, la serie se ve así: 0, 1, 1, 2, 3, 5, 8, 13, 21 ... Las observaciones interesantes para notar 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 los números de la serie de fibonacci para dividir el rango, se divide en la misma proporción que antes.

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 por encontrar primero el número en la serie de Fibonacci más cercano pero más largo que la longitud de la matriz. Esto ocurre cuando fibonacciNumberestá en 13, que es solo más que la longitud del arreglo - 10.
A continuación, comparamos los elementos de la matriz y, sobre la base de esa comparación, realizamos una de las siguientes acciones:
  • Compare el elemento a buscar con el elemento at 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 fibonacciNumberfibonacciMinus1y en fibonacciMinus2consecuencia. El desplazamiento se restablece al índice actual.
  • Si elementToSearches más pequeño que el elemento actual, retrocedemos dos pasos en la serie de fibonacci y cambiamos los valores de fibonacciNumberfibonacciMinus1y en fibonacciMinus2consecuencia.
Salida:
67 found at Index 5  

Complejidad del tiempo

El peor caso de complejidad de tiempo para esta búsqueda es O (log (N)) .

Complejidad espacial

Mientras que 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 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 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, veamos brevemente la forma en que se realiza la búsqueda en diferentes colecciones de Java.

Arrays

Los arreglos en Java se pueden buscar usando uno de los java.util.BinarySearchmétodos. La búsqueda binaria en la versión Open JDK usa 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 la lista

La interfaz de la lista tiene principalmente dos métodos que se pueden usar para buscar: indexOf()contains().
El indexOf()método devuelve el índice del elemento si existe en la lista o -1si no existe.
El contains()método devuelve truefalsedependiendo de la existencia del elemento. Llama internamente al indexOf()método.
La interfaz de la lista utiliza la búsqueda secuencial para realizar la búsqueda del índice y, por lo tanto, su complejidad de tiempo es O(N).
Probemos una operación de búsqueda en un 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 par clave-valor. La Mapinterfaz en Java utiliza tanto la HashBasedbúsqueda como la Binary Search Tree.
La java.util.HashMapclase utiliza un valor hash de keypara almacenar los elementos en el mapa. Recuperar el elemento del Mapa usando las teclas correctas para el hash y un buen algoritmo de Hashing (de modo que no se produzcan colisiones) es O(1).
Otra implementación de la interfaz del mapa es la java.util.TreeMap, que utiliza internamente el árbol rojo-negro, que es un tipo de árbol de búsqueda binaria con equilibrio automático. Los elementos agregados a este árbol se almacenan automáticamente de forma ordenada por el árbol.
La complejidad del tiempo de 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, se 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 usar para determinar si una clave dada 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 la búsqueda BinaryHash-based.
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 un índice en la Setinterfaz y, como tal, la operación de búsqueda contains()regresa truefalsedepende de la existencia del elemento que se está buscando.
En este caso, dado que el elemento existe en el conjunto, obtenemos la siguiente salida:
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 se desempeñan.
Busquemos el elemento 573400en una matriz ordenada que se llena con un millón de enteros.
Aquí están los resultados de los algoritmos:
tiempo (ns)LinealBinario (iterativo)Binario (Recursivo)SaltarInterpolaciónExponencialFibonacci
Primer intento5 229 90123 01414 928125 64718 66149 76213 373
Segunda carrera8 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 lleva mucho 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 hacer mucho para determinar el rendimiento del sistema.
En este artículo, analizamos cómo funcionan los diferentes algoritmos de búsqueda y en qué circunstancias se adaptan perfectamente. También vimos cómo Java utiliza diferentes algoritmos de búsqueda en su API de colecciones integrada.
Como siempre, puede encontrar el código fuente de los algoritmos descritos en este artículo aquí .

Acerca de: Programator

Somos Instinto Programador

0 comentarios:

Publicar un comentario

Dejanos tu comentario para seguir mejorando!

Con tecnología de Blogger.