🗺️ Linear & Binary search
Written by Dani Sanchez
Actualmente sigo estudiando el libro “A Common-Sense Guide to Data Structures and Algorithms” y uno de los primeros temas que trata son las búsquedas en listas de datos.
Es un tema básico, lo sé. Pero el autor lo expone para hacerle ver al lector la importancia del algoritmo y la estructura de datos que decide utilizar.
En este artículo me gustaría dar una pequeña introducción a linear search y binary search y qué ventajas aportan.
Un poco de contexto
Primero de todo, comprender las dos estructuras de datos que vamos a mencionar en el artículo.
Arrays y Array-based Sets.
Array
- Lista de datos.
- Pueden estar ordenados o no.
- No tienen porqué ser únicos.
Array-based Set
- Lista de datos.
- Ordenados.
- Únicos.
Para poder efectuar una binary search, es necesario que los elementos de la lista sean únicos y están ordenados.
Linear search
Supongamos que queremos buscar el número ‘80’ en el array anteriormente expuesto.
El sentido común hace que vayamos elemento a elemento y nos preguntemos si es el número ‘80’.
- Primer elemento. ¿Tiene como valor ‘80’? No, es ‘10’.
- Continúo con el siguiente. ¿Tiene como valor ‘80’? No, es ‘40’.
- Continúo con el siguiente, etc…
Finalmente, en el elemento cuyo índice es 5, encontraremos el número ‘80’. Con esto habremos terminado la búsqueda y el programa podrá proseguir con otras tareas.
Esto en listas con pocos elementos es aceptable, pero si por ejemplo, tenemos 10000 elementos, sería una locura. Tendríamos que revisar, en el peor de los casos, toda la longitud del array.
En términos de Big O, estaríamos hablando de O(N), la búsqueda sería tan larga como elementos tuviera la lista. A esta complejidad se le conoce también como linear time.
Para evitar este problema, existe la búsqueda binaria, o binary search.
Binary Search
La búsqueda binaria es un algoritmo de búsqueda que consiste en ir descartando conjuntos de valores. Estos al estar ordenados, permiten asegurar que si, por ejemplo, buscamos el elemento de la lista cuyo valor es ‘80’, podamos descartar todos aquellos que sean menores a ‘80’. Insisto, al estar ordenados, es relativamente sencillo.
Dada la siguiente lista, queremos buscar el elemento cuyo valor es ‘23’.
La búsqueda binaria consta de los siguientes pasos:
- Partimos la lista por la mitad. El elemento cuyo índice es 4 marca la mitad, su valor es ‘16’. ¿‘16’ es menor que ‘23’? Nos quedamos con la segunda mitad.
- Volvemos a partir la lista por la mitad. El elemento cuyo valor es ‘56’ marca la mitad. ¿’56’ es mayor que ‘23’?. Nos quedamos con la primera mitad.
- Volvemos a partir la lista por la mitad. Justo el elemento que marca la mitad tiene como valor ‘23’. El elemento coincide con el valor que estamos buscando. Devolvemos 5, el índice del elemento cuyo valor es ‘23’.
Como se puede apreciar, este algoritmo es increíblemente más rápido que la búsqueda lineal. En términos de Big O sería O(log N), también llamado logarithmic time.
Un algoritmo cuya time complexity es de O(log N), significa que tomará tantos pasos como sea necesario para seguir reduciendo a la mitad los elementos hasta que nos quedemos con uno solo.
Revisando otra vez en detalle la búsqueda binaria es justamente lo que estamos haciendo. Partir la lista de elementos hasta dar con el elemento deseado.
Big O Notation
Más adelante me gustaría indagar en profundidad sobre Big O.
Por ahora, una pequeña comparativa:
Y aquí algunos datos recogidos de diferentes pruebas, en base a un número de elementos y el número de pasos o steps que el algoritmo realiza:
| Núm. Elementos | O(N) | O(log N) |
|---|---|---|
| 8 | 8 | 3 |
| 16 | 16 | 4 |
| 32 | 32 | 5 |
| 64 | 64 | 6 |
| 128 | 128 | 7 |
| 256 | 256 | 8 |
| 512 | 512 | 9 |
| 1024 | 1024 | 10 |
Mientras O(N) toma tantos pasos como elementos haya, O(log N) solo toma uno más cada vez que los elementos se duplican.
Esto es todo por ahora, espero que hayas disfrutado de esta pequeña introducción a ciertos algoritmos de búsqueda y a Big O.
Dejo también la URL a mi repo donde voy publicando los algoritmos, https://github.com/danisanga/java-performance-tests.
Estoy trabajando en una solución que permita medir la performance de cada uno de ellos (simplemente a nivel orientativo).