Explicación de los algoritmos de búsqueda lineal y binaria
La capacidad de buscar algunos datos es un aspecto importante de la informática. Los algoritmos de búsqueda se utilizan para buscar un elemento en particular en un conjunto de datos.
Los algoritmos devuelven un resultado booleano (verdadero o falso) a una consulta de búsqueda. También se pueden modificar para dar la posición relativa del valor encontrado.
Para este artículo, los algoritmos se concentrarán en determinar si existe un valor.
Algoritmos de búsqueda lineal
La búsqueda lineal también se conoce como búsqueda secuencial. En este tipo de búsqueda, cada valor de una lista se visita uno a uno de forma ordenada mientras se comprueba si existe el valor deseado.
El algoritmo verifica valor por valor hasta que encuentra el valor que está buscando o se queda sin valores para buscar. Cuando se queda sin valores para buscar, eso significa que su consulta de búsqueda no existe en la lista.
Un algoritmo de búsqueda secuencial toma una lista de valores y el elemento deseado en la lista como sus parámetros. El resultado devuelto se inicializa como Falso y cambiará a Verdadero cuando se encuentre el valor deseado.
Vea la implementación de Python a continuación como ejemplo:
def linearSearch (mi lista, artículo):
encontrado = Falso
índice = 0
while index <len (mylist) y no encontrado:
si mi lista [índice] == artículo:
encontrado = Verdadero
demás:
índice = índice + 1
retorno encontrado
Análisis de algoritmos
El mejor de los casos ocurre cuando el elemento deseado es el primero en la lista. El peor de los casos ocurre cuando el elemento deseado es el último de la lista (el n-ésimo elemento). Por lo tanto, la complejidad de tiempo para la búsqueda lineal es O (n).
El escenario de caso promedio en el algoritmo anterior es n / 2.
Búsqueda lineal modificada
Es importante saber que el algoritmo utilizado asume que se le proporciona una lista aleatoria de elementos. Es decir, los elementos de la lista no están en ningún orden en particular.
Suponga que los elementos están en un orden particular, digamos de menor a mayor. Sería posible lograr alguna ventaja en el cálculo.
Tome un ejemplo de buscar 19 en la lista dada: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Después de llegar a 23, quedará claro que el elemento que se busca no existe en la lista. Por lo tanto, ya no sería importante seguir buscando en el resto de elementos de la lista.
Algoritmos de búsqueda binaria
Ha visto cómo una lista ordenada puede reducir el cálculo necesario. El algoritmo de búsqueda binaria aprovecha aún más esta eficiencia que la que presenta tener una lista ordenada.
El algoritmo comienza tomando un valor medio de una lista ordenada y verificando si es el valor deseado. Si no es así, entonces se verifica el valor si es menor o mayor que el valor deseado.
Si es menos, entonces no es necesario consultar la mitad inferior de la lista. De lo contrario, si es mayor, pasa a la mitad superior de la lista.
Independientemente de la sublista que se elija (izquierda o derecha), se volverá a determinar el valor medio. El valor se vuelve a comprobar si es el valor requerido. Si no es así, se comprueba si es menor o mayor que el valor solicitado.
Este proceso se repite hasta que se encuentra un valor si está allí.
La implementación de Python a continuación es para el algoritmo de búsqueda binaria.
def binarySearch (mi lista, artículo):
bajo = 0
alto = len (mi lista) – 1
encontrado = Falso
mientras bajo <= alto y no encontrado:
medio = (bajo + alto) // 2
if mylist [mid] == item:
encontrado = Verdadero
elemento elif <mylist [mid]:
alto = medio – 1
demás:
bajo = medio + 1
retorno encontrado
Análisis de algoritmos
El mejor de los casos ocurre cuando se encuentra que el artículo deseado es el artículo del medio. Sin embargo, el peor de los casos no es tan sencillo. Siga el análisis a continuación:
Después de la primera comparación, quedarán n / 2 elementos. Después del segundo, quedarán n / 4 elementos. Después del tercero, n / 8.
Observe que el número de elementos se reduce a la mitad hasta que llegan a n / 2i, donde i es el número de comparaciones. Después de toda la división, terminamos con solo 1 artículo.
Esto implica:
n / 2i = 1
Por lo tanto, la búsqueda binaria es O (log n).
Pasando a la clasificación
En la búsqueda binaria, consideramos un caso en el que la matriz dada ya estaba ordenada. Pero suponga que tiene un conjunto de datos desordenado y desea realizar una búsqueda binaria en él. ¿Qué harías?
La respuesta es simple: ordénelo. Hay una serie de técnicas de clasificación en informática que han sido bien investigadas. Una de estas técnicas que puede comenzar a estudiar es el algoritmo de clasificación de selección, mientras que también tenemos muchas guías relacionadas con otras áreas.