Búsqueda en la estructura de datos: explicación de los diferentes métodos de búsqueda
Publicado: 2021-05-03¡La red de comunicación se está expandiendo, por lo que la gente está usando Internet! Las empresas se están volviendo digitales para una gestión eficiente. Los datos generados en Internet están aumentando y, por lo tanto, los conjuntos de datos se están volviendo complejos. Es esencial organizar, administrar, acceder y analizar los datos con cuidado y eficiencia, una estructura de datos es la técnica más útil, ¡y el artículo se enfoca en lo mismo!
Tabla de contenido
Estructura de datos
En informática, las estructuras de datos son la base para los tipos de datos abstractos (ADT), donde ADT son la forma lógica del tipo de datos. El diseño físico del tipo de datos se implementa utilizando la estructura de datos. Se utilizan diferentes tipos de estructuras de datos para diferentes tipos de aplicaciones; algunos están especializados en tareas particulares.
La estructura de datos es una colección de valores de datos y relaciones entre ellos, operaciones y funciones aplicables a los datos. Ayuda a organizar, administrar y almacenar datos en un formato particular. Por lo tanto, los usuarios pueden acceder fácilmente y modificar los datos de manera eficiente.
Las estructuras de datos ayudan a administrar grandes cantidades de datos, como bases de datos masivas. Los algoritmos eficientes se construyen sobre la base de estructuras de datos eficientes. Además del almacenamiento eficiente, las estructuras de datos también son responsables de la recuperación eficiente de información de la memoria almacenada. Incluye una matriz, lista enlazada, puntero, búsqueda, pila, gráfico, cola, estructura, programas, clasificación, etc.
El artículo cubre el concepto de búsqueda en la estructura de datos y sus métodos. Se explican en detalle dos ejemplos de algoritmos para entender claramente el concepto. Para obtener más conocimientos, habilidades y experiencia, hay disponibles cursos en línea sobre estructura de datos, que se mencionan al final del artículo.
¿Qué es la búsqueda en la estructura de datos?
El proceso de encontrar la información deseada del conjunto de elementos almacenados en forma de elementos en la memoria de la computadora se denomina "búsqueda en la estructura de datos". Estos conjuntos de elementos tienen varias formas, como una matriz, un árbol, un gráfico o una lista enlazada. Otra forma de definir la búsqueda en la estructura de datos es ubicar el elemento deseado de características específicas en una colección de elementos.
Métodos de búsqueda
La búsqueda en la estructura de datos se puede realizar implementando algoritmos de búsqueda para verificar o recuperar un elemento de cualquier forma de estructura de datos almacenada. Estos algoritmos se clasifican en función de su tipo de operación de búsqueda, como:
- Búsqueda secuencial
La matriz o lista de elementos se recorre secuencialmente mientras se verifica cada componente del conjunto.
Por ejemplo, Búsqueda lineal.
- Búsqueda de intervalo
Los algoritmos diseñados explícitamente para buscar en estructuras de datos ordenados se incluyen en la búsqueda por intervalos. La eficiencia de estos algoritmos es mucho mejor que la de los algoritmos de búsqueda lineal.
Por ejemplo, búsqueda binaria, búsqueda logarítmica.
Estos métodos se examinan en función del tiempo que tarda un algoritmo en buscar un elemento que coincida con el elemento de búsqueda en las recopilaciones de datos y están dados por,
- El mejor momento posible
- el tiempo promedio
- El peor momento
Las preocupaciones principales se relacionan con los peores tiempos que conducen a predicciones garantizadas del rendimiento del algoritmo y también son fáciles de calcular en comparación con los tiempos promedio.
Para ilustrar ejemplos y conceptos en este artículo, se consideran elementos 'n' en la recopilación de datos en cualquier formato de datos. Las operaciones dominantes se utilizan para simplificar el análisis y la comparación de algoritmos. Para buscar en una estructura de datos, una comparación es una operación dominante, que se denota con O() y se pronuncia como "gran-Oh" o "Oh".
Existen numerosos algoritmos de búsqueda en una estructura de datos, como la búsqueda lineal, la búsqueda binaria, la búsqueda por interpolación, la búsqueda por salto, la búsqueda exponencial, la búsqueda de Fibonacci, la búsqueda de sublistas, la búsqueda binaria ubicua, la búsqueda binaria ilimitada, la función recursiva para la búsqueda de subcadenas y el programa recursivo. para buscar un elemento linealmente en la matriz dada. El artículo se limita a los algoritmos de búsqueda lineal y binaria y sus principios de funcionamiento.
Obtengamos información detallada sobre la búsqueda lineal y la búsqueda binaria en la estructura de datos.
Búsqueda lineal
El algoritmo de búsqueda lineal busca todos los elementos en la matriz secuencialmente. Su mejor tiempo de ejecución es uno, mientras que el peor tiempo de ejecución es n, donde n es el número total de elementos en la matriz de búsqueda.
Es el algoritmo de búsqueda más simple en la estructura de datos y verifica cada elemento en el conjunto de elementos hasta que coincida con el elemento de búsqueda hasta el final de la recopilación de datos. Cuando los datos no están ordenados, se prefiere un algoritmo de búsqueda lineal.
La búsqueda lineal tiene algunas complejidades como se indica a continuación:
- Complejidad espacial
La complejidad del espacio para la búsqueda lineal es O(n) ya que no utiliza ningún espacio extra donde n es el número de elementos en una matriz.
- Complejidad del tiempo
*Complejidad en el mejor de los casos = O(1) se produce cuando el elemento de búsqueda está presente en el primer elemento de la matriz de búsqueda.
*Complejidad en el peor de los casos = O(n) se produce cuando el elemento de búsqueda no está presente en el conjunto de elementos o matriz.
*Se hace referencia a la complejidad media = O(n) cuando el elemento está presente en algún lugar de la matriz de búsqueda.
Ejemplo,
Tomemos una matriz de elementos como se indica a continuación:
45, 78, 12, 67, 08, 51, 39, 26
Para encontrar '51' en una matriz de 8 elementos dada anteriormente, un algoritmo de búsqueda lineal verificará cada elemento secuencialmente hasta que su puntero apunte a 51 en el espacio de memoria. Toma O(6) tiempo encontrar 51 en una matriz. Para encontrar 12, en la matriz anterior, se necesita O(3), mientras que para 26 se requiere O(8) de tiempo.
Búsqueda binaria
Este algoritmo encuentra elementos específicos comparando los elementos intermedios en la recopilación de datos. Cuando se produce una coincidencia, devuelve el índice del elemento. Cuando el elemento del medio es mayor que el elemento, busca un elemento central del subarreglo izquierdo. Por el contrario, si el elemento del medio es más pequeño que el elemento de búsqueda, explora el medio del elemento en el subconjunto derecho. Continúa buscando un elemento hasta que lo encuentra o hasta que el tamaño de los subconjuntos se vuelve cero.
La búsqueda binaria necesita un orden ordenado de elementos. Es más rápido que un algoritmo de búsqueda lineal. Funciona según el principio divide y vencerás.
Complejidad en tiempo de ejecución = O (log n)
El algoritmo de búsqueda binaria tiene complejidades como se indica a continuación:
- Complejidad en el peor de los casos = O (n log n)
- Complejidad media = O (n log n)
- Complejidad del mejor caso = O (1)
Ejemplo,
Tomemos un algoritmo ordenado de 08 elementos:
08, 12, 26, 39, 45, 51, 67, 78
Para encontrar 51 en una matriz de los elementos anteriores,
El algoritmo dividirá una matriz en dos matrices, 08, 12, 26, 39 y 45, 51, 67, 78
Como 51 es mayor que 39, comenzará a buscar elementos en el lado derecho de la matriz.
Además dividirá el en dos como 45, 51 y 67, 78
Como 51 es más pequeño que 67, comenzará a buscar a la izquierda de ese subarreglo.
Ese subarreglo se divide nuevamente en dos como 45 y 51.
Como 51 es el número que coincide con el elemento de búsqueda, devolverá su número de índice de ese elemento en la matriz.
Concluirá que el elemento de búsqueda 51 está ubicado en la sexta posición en una matriz.
La búsqueda binaria reduce el tiempo a la mitad, ya que el recuento de comparación se reduce significativamente en comparación con el algoritmo de búsqueda lineal.
Leer: Tipos de estructuras de datos en Python
Búsqueda de interpolación
Es una variante mejorada del algoritmo de búsqueda binaria y funciona en la posición de sondeo del elemento de búsqueda. Similar a los algoritmos de búsqueda binaria, funciona de manera eficiente solo en la recopilación de datos ordenados.
Peor tiempo de ejecución = O(n)
Cuando se conoce la ubicación del elemento de destino en la recopilación de datos, se utiliza una búsqueda por interpolación. Para encontrar un número en la guía telefónica, si desea buscar el número de teléfono de Mónica, en lugar de utilizar una búsqueda lineal o binaria, puede sondear directamente el espacio de memoria donde los nombres comienzan con 'M'.
Conclusión
Buscar en estructuras de datos se refiere a encontrar un elemento dado en la matriz de 'n' elementos. Hay dos categorías, a saber. Búsqueda secuencial y búsqueda por intervalos en la búsqueda. Casi todos los algoritmos de búsqueda se basan en una de estas dos categorías. Las búsquedas lineales y binarias son los dos algoritmos simples y fáciles de implementar en los que el binario funciona más rápido que los algoritmos lineales.
Aunque la búsqueda lineal es más sencilla, verifica cada elemento hasta que encuentra una coincidencia con el elemento de búsqueda, por lo que es eficiente cuando la recopilación de datos no se ordena correctamente. Pero, si la recopilación de datos está ordenada y la longitud de una matriz es considerable, la búsqueda binaria es más rápida.
La estructura de datos es una parte esencial de la programación de computadoras cuando se trata de conjuntos de datos. Los programadores y desarrolladores necesitan seguir actualizándose y mejorando sus habilidades con conceptos básicos y actualizaciones en técnicas de programación informática. Los programadores que se ocupan de la estructura de datos deberían optar por cursos a menudo.
Si tiene curiosidad por obtener más información sobre la ciencia de datos, consulte el Programa PG ejecutivo en ciencia de datos de IIIT-B y upGrad, creado para profesionales que trabajan y ofrece más de 10 estudios de casos y proyectos, talleres prácticos, tutoría con expertos de la industria, 1 a 1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.
