1. Información general
En este artículo, cubriremos las ventajas de una búsqueda binaria sobre una búsqueda lineal simple y explicaremos su implementación en Java.
2. Necesidad de una búsqueda eficiente
Digamos que estamos en el negocio de venta de vinos y millones de compradores visitan nuestra aplicación todos los días.
A través de nuestra aplicación, un cliente puede filtrar los artículos que tienen un precio inferior a n dólares, seleccionar una botella de los resultados de búsqueda y agregarlos a su carrito. Tenemos millones de usuarios que buscan vinos con un límite de precio cada segundo. Los resultados deben ser rápidos.
En el backend, nuestro algoritmo ejecuta una búsqueda lineal a través de toda la lista de vinos comparando el límite de precio ingresado por el cliente con el precio de cada botella de vino en la lista.
Luego, devuelve los artículos que tienen un precio menor o igual que el límite de precio. Esta búsqueda lineal tiene una complejidad temporal de O (n) .
Esto significa que cuanto mayor sea la cantidad de botellas de vino en nuestro sistema, más tiempo llevará. El tiempo de búsqueda aumenta proporcionalmente al número de elementos nuevos introducidos.
Si comenzamos a guardar elementos en orden ordenado y buscamos elementos mediante la búsqueda binaria, podemos lograr una complejidad de O (log n) .
Con la búsqueda binaria, el tiempo que toman los resultados de la búsqueda aumenta naturalmente con el tamaño del conjunto de datos, pero no de manera proporcional.
3. Búsqueda binaria
En pocas palabras, el algoritmo compara el valor de la clave con el elemento central de la matriz; si son desiguales, se elimina la mitad en la que la clave no puede formar parte, y la búsqueda continúa por la mitad restante hasta que se logra.
Recuerde: el aspecto clave aquí es que la matriz ya está ordenada.
Si la búsqueda termina con la mitad restante vacía, la clave no está en la matriz.
3.1. Impl iterativo
public int runBinarySearchIteratively( int[] sortedArray, int key, int low, int high) { int index = Integer.MAX_VALUE; while (low <= high) { int mid = (low + high) / 2; if (sortedArray[mid] key) { high = mid - 1; } else if (sortedArray[mid] == key) { index = mid; break; } } return index; }El método runBinarySearchIteratively toma un sortedArray , key y los índices bajo y alto de sortedArray como argumentos. Cuando el método se ejecuta por primera vez, el bajo , el primer índice de sortedArray, es 0, mientras que el alto , el último índice de sortedArray, es igual a su longitud - 1.
El medio es el índice medio de sortedArray . Ahora, el algoritmo se ejecuta un mientras bucle de la comparación de la clave con el valor de la matriz del índice medio de la sortedArray .
3.2. Impl recursivo
Ahora, echemos un vistazo también a una implementación simple y recursiva:
public int runBinarySearchRecursively( int[] sortedArray, int key, int low, int high) { int middle = (low + high) / 2; if (high < low) { return -1; } if (key == sortedArray[middle]) { return middle; } else if (key < sortedArray[middle]) { return runBinarySearchRecursively( sortedArray, key, low, middle - 1); } else { return runBinarySearchRecursively( sortedArray, key, middle + 1, high); } } El método runBinarySearchRecursively acepta un sortedArray , clave, los índices bajo y alto de sortedArray .
3.3. Usando matrices. búsqueda binaria()
int index = Arrays.binarySearch(sortedArray, key); Un sortedArray y una clave int , que se buscará en la matriz de enteros, se pasan como argumentos al método binarySearch de la clase Java Arrays .
3.4. Usando colecciones. búsqueda binaria()
int index = Collections.binarySearch(sortedList, key); Una sortedList y una clave Integer , que se buscará en la lista de objetos Integer , se pasan como argumentos al método binarySearch de la clase Colecciones de Java .
3.5. Actuación
El uso de un enfoque recursivo o iterativo para escribir el algoritmo es principalmente una cuestión de preferencia personal. Pero todavía hay algunos puntos que debemos tener en cuenta:
1. La recursividad puede ser más lenta debido a la sobrecarga de mantener una pila y, por lo general, ocupa más memoria.
2. La recursividad no es apta para pilas . Puede causar StackOverflowException al procesar grandes conjuntos de datos
3. La recursividad agrega claridad al código, ya que lo hace más corto en comparación con el enfoque iterativo.
Idealmente, una búsqueda binaria realizará un menor número de comparaciones en contraste con una búsqueda lineal de valores grandes de n. Para valores más pequeños de n, la búsqueda lineal podría funcionar mejor que una búsqueda binaria.
Se debe saber que este análisis es teórico y puede variar según el contexto.
Además, el algoritmo de búsqueda binaria necesita un conjunto de datos ordenados que también tiene sus costos . Si usamos un algoritmo de clasificación por fusión para clasificar los datos, se agrega una complejidad adicional de n log n a nuestro código.
Entonces, primero debemos analizar bien nuestros requisitos y luego tomar una decisión sobre qué algoritmo de búsqueda se adaptaría mejor a nuestros requisitos.
4. Conclusión
Este tutorial demostró una implementación de algoritmo de búsqueda binaria y un escenario en el que sería preferible usarlo en lugar de una búsqueda lineal.
Busque el código del tutorial en GitHub.