introduction searching algorithms c
Una descripción general de los algoritmos de búsqueda en C ++.
Seguimos buscando algo u otro en nuestra vida cotidiana. Al igual que en nuestra vida diaria, como profesionales del software, necesitamos buscar información en nuestra computadora. La recuperación de información debe realizarse con rapidez, ya que no podemos permitirnos perder gran parte de nuestro tiempo buscando información.
Por lo tanto, necesitamos algunas técnicas de búsqueda o algoritmos eficientes que puedan buscar una determinada información en poco tiempo y entregársela al usuario para que pueda seguir adelante con las otras tareas.
=> Visite aquí para ver la lista completa de tutoriales de C ++.
Lo que vas a aprender:
Técnicas de búsqueda
Tenemos dos técnicas de búsqueda principales que se emplean principalmente para buscar información.
Éstos incluyen:
- Búsqueda lineal
- Búsqueda binaria
En este tutorial, exploraremos estas dos técnicas de búsqueda en detalle.
Búsqueda lineal
Esta es la técnica de búsqueda más básica y también es más fácil de implementar. En una búsqueda lineal, la clave a buscar se compara linealmente con cada elemento de la recopilación de datos. Esta técnica funciona eficazmente en estructuras de datos lineales.
Consideremos la siguiente matriz.
Arriba está la matriz de siete elementos. Si queremos buscar la clave = 23, comenzando desde el 0thelemento, el valor clave se comparará con cada elemento. Una vez que el elemento clave coincide con el elemento de la matriz, se devolverá esa ubicación en particular. En este caso, la ubicación, se devolverá 4 ya que el valor-clave coincide con el valor en esa ubicación.
Hemos implementado una búsqueda lineal usando C ++ y lenguaje Java a continuación.
Implementación de C ++
|_+_|Producción:
donde encuentro la llave de seguridad
La matriz de entrada es
21 43 23 54 75 13 5 8 25 10
Ingrese la clave a buscar: 3
No se pudo encontrar la clave dada en la matriz
La matriz de entrada es
21 43 23 54 75 13 5 8 25 10
Ingrese la clave a buscar: 75
Clave encontrada en la posición 5 en la matriz
Implementación de Java
|_+_|Producción:
La matriz de entrada es
21 43 23 54 75 13 5 8 25 10
Introducir clave
23
llave encontrada en la ubicación 3
La búsqueda lineal se puede realizar en cualquier estructura de datos lineal que tenga elementos ordenados o no ordenados. Pero lleva más tiempo si hay demasiados elementos y si el elemento clave está hacia el final, ya que cada elemento se compara con el valor clave.
Búsqueda binaria
La búsqueda binaria es una técnica que utiliza la técnica de 'divide y vencerás' para buscar una clave. Funciona en una lista lineal ordenada de elementos. La lista ordenada es el requisito básico para que funcione una búsqueda binaria.
En el método de búsqueda binaria, la lista se divide repetidamente por la mitad y el elemento clave se busca en ambas mitades de la lista hasta que se encuentra la clave.
Por ejemplo,tomemos la siguiente matriz ordenada de 10 elementos.
Digamos que la clave = 21 debe buscarse en la matriz.
Calculemos la ubicación media de la matriz.
dfs y bfs c ++
Medio = 0 + 9/2 = 4
Por ejemplo,tomemos la siguiente matriz ordenada de 10 elementos.
Clave = 21
Primero, compararemos el valor clave con el elemento (mid). Encontramos que el valor del elemento en mid = 21.
Por lo tanto, encontramos que key = (mid). De ahí que se encuentre la clave.
clave = 25
Primero comparamos el valor de la clave con mid. Entonces (21<25), we will directly search for the key in the upper half of the array.
Ahora de nuevo encontraremos el medio de la mitad superior de la matriz.
Medio = 4 + 9/2 = 6
El valor en la ubicación (mid) = 25
Ahora comparamos el elemento clave con el elemento medio. Entonces (25 == 25), así hemos encontrado la clave en la ubicación (mid).
Dividimos repetidamente la matriz y comparando el elemento clave con el medio, decidimos en qué mitad buscar la clave.
A continuación se muestra la implementación de C ++ y Java para la búsqueda binaria.
Implementación de C ++
|_+_|Producción:
La matriz de entrada es
5 8 10 13 21 23 25 43 54 75
Introduzca la clave que desea buscar: 21
Llave encontrada en la ubicación 5
Implementación de Java
|_+_| Producción:
La matriz de entrada es
5 8 10 13 21 23 25 43 54 75
Ingrese la clave a buscar
mejor programa para clonar un disco duro
21
la ubicación de la llave es 5
La búsqueda binaria es más eficiente en términos de tiempo y corrección. La técnica de búsqueda lineal rara vez se utiliza ya que es más engorrosa y lenta. La búsqueda binaria es mucho más rápida en comparación con una búsqueda lineal.
Conclusión
Las técnicas de búsqueda nos ayudan a buscar la información almacenada en un ordenador para que el usuario pueda continuar con las demás tareas del tratamiento de la información. La técnica de búsqueda lineal es simple y más fácil, pero no se usa mucho.
La técnica de búsqueda binaria es mucho más rápida y eficiente, por lo que se usa ampliamente.
En nuestro próximo tutorial, exploraremos las diversas técnicas de clasificación en detalle.
=> Consulte la guía de formación perfecta de C ++ aquí.
Lectura recomendada
- Introducción al lenguaje de programación Java - Tutorial en vídeo
- Introducción a Appium Studio: beneficios y características clave
- Algoritmos en STL
- La mejor serie de tutoriales de C # GRATIS: la guía definitiva de C # para principiantes
- Video 1 de JMeter: Introducción, descarga e instalación de JMeter
- Proceso de introducción e instalación de Python
- Qué es Unix: una breve introducción a Unix
- Introducción a Micro Focus LoadRunner: prueba de carga con el tutorial n. ° 1 de LoadRunner