Guías de Make it Real
Search…
Búsqueda
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:
1
BinarySearch(lista, elem)
2
Retorne BinarySearchRecursive(lista, elem, 0, lista.length)
3
4
BinarySearchRecursive(lista, elem, inicio, fin)
5
Si inicio es mayor a fin
6
Retorne -1
7
8
mitad = mitad entre inicio y fin
9
Si el valor en la posición mitad es igual a elem
10
Retorne mitad
11
Si el valor en la posición mitad es menor a elem
12
Retorne BinarySearchRecursive(lista, elem, mitad + 1, fin)
13
Si el valor en la posición mitad es mayor a elem
14
Retorne BinarySearchRecursive(lista, elem, inicio, mitad - 1)
Copied!
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.Last modified 3yr ago
Copy link