Introducción al algoritmo de búsqueda lineal: introducción y características [con ejemplos]

¿Qué es la búsqueda?

La búsqueda es el proceso de encontrar un elemento dado en una lista de elementos. Ayuda en la búsqueda de un registro en particular. Por lo tanto, es una técnica de identificación del lugar de un elemento dado. El éxito de un proceso de búsqueda depende de si el elemento a buscar ha sido identificado o no.

La estructura de datos permite la búsqueda de datos a través de dos métodos.

1. Búsqueda lineal o búsqueda secuencial
2. Búsqueda binaria

Búsqueda lineal

Los algoritmos de búsqueda lineal son un tipo de algoritmo para la búsqueda secuencial de los datos. Este algoritmo encuentra un elemento dado con complejidad O(n). Se aplica a una colección de artículos. Todos y cada uno de los elementos de los datos se buscan secuencialmente y se devuelven si coinciden con el elemento buscado. Si no se encuentran coincidencias, la búsqueda continúa hasta el final de los datos recopilados. Es básicamente una técnica de exploración de cada elemento mientras se recorre la lista. El algoritmo de búsqueda se puede aplicar tanto a los datos ordenados como a los no ordenados. Prácticamente, la búsqueda lineal rara vez se usa debido a las opciones de búsqueda más rápidas proporcionadas por otros algoritmos de búsqueda, como los algoritmos de búsqueda binaria y las tablas hash.

Pasos en el algoritmo de búsqueda lineal

• Lectura del elemento de búsqueda por parte del usuario.
• El elemento a buscar se comprime con el primer elemento de la lista.
• Si los elementos coinciden, se genera una devolución.
• Si los elementos no coinciden, el elemento a buscar se compara con el segundo elemento de la lista.
• El proceso se repite hasta que se empareja el elemento.

Características de los algoritmos de búsqueda lineal

1. Por lo general, se aplica a una pequeña lista de datos sin clasificar o desordenados.
2. El tiempo depende linealmente del número de elementos, por lo que tiene una complejidad temporal si O(n).
3. La implementación es muy simple.

Algoritmos de búsqueda lineal

Un método de bucle continuo continúa a menos y hasta que se encuentre el elemento

• algoritmo Seqnl_Search (lista, artículo)
• Pre: lista != ;
• Publicar: devolver el índice del elemento si se encuentra, de lo contrario: 1
• índice <-fi
• while index < list.Cnt and list[index] != item //cnt: variable de contador
• índice <- índice + 1
• terminar mientras
• si índice < lista.Cnt y lista[índice] = artículo
• índice de retorno
• terminara si
• retorno: 1
• fin Seqnl_Search

Ejemplo de búsqueda lineal

Problema: Dada una matriz arr[] de n elementos, escriba una función para buscar un elemento dado x en arr[].

Figura 1: Un ejemplo de código que muestra la implementación del algoritmo de búsqueda lineal

Fuente

Los algoritmos de búsqueda lineal se pueden utilizar en varios lenguajes de programación.

1. Búsqueda lineal en Python

Figura 2: Un ejemplo de código que muestra un algoritmo de búsqueda lineal en lenguaje Python

Fuente

Salida: El elemento está presente en el índice 3

2. Búsqueda lineal en C

Figura 3: Un ejemplo de código que muestra un algoritmo de búsqueda lineal en lenguaje C

Fuente

Salida : el elemento está presente en el índice 3

3. Búsqueda lineal en estructura de datos

El pseudocódigo para un problema de búsqueda lineal en la estructura de datos es

Figura 4: El pseudocódigo para el algoritmo de búsqueda lineal

Fuente

Búsqueda binaria

La búsqueda binaria es un algoritmo para buscar elementos en una matriz de elementos. En comparación con el algoritmo de búsqueda lineal, el algoritmo de búsqueda binaria se aplica a una lista ordenada de datos.

El algoritmo de búsqueda binaria incluye los siguientes pasos

• Comparación del elemento a buscar con el elemento del medio de la lista o matriz.
• Si el elemento coincide con el elemento de la lista, devuelve el índice del elemento central.
• Si no se devuelve ninguna coincidencia, se comprueba si el elemento es mayor o menor que el elemento del medio.
• Para un elemento de mayor valor que el elemento del medio, la búsqueda se realiza en el lado derecho de la matriz.
• De manera similar, si el valor del elemento es menor que el del medio, la búsqueda se realiza en el lado izquierdo de la lista.

Por lo tanto, la búsqueda binaria se aplica mejor cuando los datos contienen un gran número de elementos de barra ordenados. Esto hace que sea un requisito para el algoritmo de búsqueda que la lista/matriz esté ordenada.

Características de la búsqueda binaria

• El algoritmo de búsqueda binaria es útil para buscar una gran cantidad de elementos en una matriz.
• El algoritmo de búsqueda binaria tiene una complejidad temporal de O(logn).
• La implementación de un algoritmo de búsqueda binaria es simple.

Algoritmo de búsqueda binaria

• Algoritmo Binary_Search (lista, artículo)
• Establezca L en 0 y R en n: 1
• si L > R, entonces Binary_Search termina como fallido
• demás
• Establezca m (la posición en el elemento medio) en el piso de (L + R) / 2
• si Am < T, establezca L en m + 1 y vaya al paso 3
• si Am > T, establezca R en m: 1 y vaya al paso 3
• Ahora, Am = T,
• la búsqueda está hecha; volver (m)

Conclusión

En este artículo, analizamos qué es un algoritmo de búsqueda lineal y también estudiamos en detalle cómo buscar un determinado elemento de una lista utilizando el algoritmo de búsqueda lineal. Por último, también vimos cómo prácticamente podíamos implementar el algoritmo de búsqueda lineal usando Python 3 como lenguaje y obtener el resultado deseado.

Si está interesado en la ciencia de datos, debe consultar el programa Executive PG en ciencia de datos de IIIT-B y upGrad, que se ha diseñado cuidadosamente para profesionales que trabajan y ofrece numerosos estudios de casos, talleres prácticos, tutoría 1 a 1 y mucho más.