Los algoritmos de búsqueda nos permiten encontrar un elemento dentro de una estructura de datos (p.e. una lista, un árbo, un grafo, etc.). En este capítulo vamos a hablar exclusivamente de búsqueda en listas.
Listas
Existen dos algoritmos para buscar un elemento en una lista: la búsqueda lineal y la búsqueda binaria (que require que la lista esté ordenada).
En la sección Descripción de un algoritmo hablamos de la búsqueda lineal, que quiza es uno de los algoritmos más simples: se recorre toda la lista hasta encontrar el elemento.
La búsqueda lineal es O(n). Sin embargo, si la lista está ordenada podemos utilizar la búsqueda binaria, que es O(log n).
Búsqueda binaria
1
Entrada:
2
* lista: arreglo de elementos
3
* valor: el valor que estamos buscando
4
5
Salida: la posición en la que se encuentra el valor (o -1 si no lo encuentra)
6
7
Prerequisitos: la lista se encuentra ordenada
Copied!
La búsqueda binaria sigue la estrategia de divide y vencerás. Aprovechando que la lista está ordenada iniciamos comparando el elemento que buscado con el valor que se encuentra en la mitad de la lista. Si el elemento es mayor (o menor) podemos descartar la otra mitad y volver a repetir el proceso en la mitad donde esperamos encontrar el elemento.
Este algoritmo se puede escribir de forma recursiva:
La función recursiva necesita algunos argumentos adicionales así que utilizamos una función adicional BinarySearchRecursive y la invocamos desde la función principal BinarySearch.