Contenido

• Cuadro comparativo
• Definición de búsqueda lineal
• Definición de búsqueda binaria
• Conclusión

La búsqueda lineal y la búsqueda binaria son los dos métodos que se utilizan en matrices para buscando los elementos. La búsqueda es un proceso de encontrar un elemento dentro de la lista de elementos almacenados en cualquier orden o al azar.

La principal diferencia entre la búsqueda lineal y la búsqueda binaria es que la búsqueda binaria tarda menos tiempo en buscar un elemento de la lista ordenada de elementos. Por lo tanto, se infiere que la eficiencia del método de búsqueda binaria es mayor que la búsqueda lineal.

Otra diferencia entre los dos es que hay un requisito previo para la búsqueda binaria, es decir, los elementos deben ser ordenado mientras que en la búsqueda lineal no existe tal requisito previo. Aunque ambos métodos de búsqueda utilizan diferentes técnicas que se analizan a continuación.

1. Cuadro comparativo
2. Definición
3. Diferencias clave
4. Conclusión

Cuadro comparativo

Bases para la comparación	Búsqueda lineal	Búsqueda binaria
Complejidad de tiempo	EN)	O (log 2 NORTE)
Mejor hora del caso	Primer elemento O (1)	Elemento central O (1)
Requisito previo para una matriz	No requerido	La matriz debe estar ordenada
El peor caso para N número de elementos	Se requieren N comparaciones	Puede concluir después de solo iniciar sesión2N comparaciones
Se puede implementar en	Matriz y lista vinculada	No se puede implementar directamente en la lista vinculada
Insertar operación	Se inserta fácilmente al final de la lista	Requerir procesamiento para insertar en su lugar adecuado para mantener una lista ordenada.
Tipo de algoritmo	De naturaleza iterativa	Divide y conquista en la naturaleza
Utilidad	Fácil de usar y sin necesidad de elementos ordenados.	De todos modos, el algoritmo y los elementos difíciles deben organizarse en orden.
Líneas de código	Menos	Más

Definición de búsqueda lineal

En una búsqueda lineal, cada elemento de una matriz se recupera uno por uno en un orden lógico y se comprueba si es el elemento deseado o no. Una búsqueda no tendrá éxito si se accede a todos los elementos y no se encuentra el elemento deseado. En el peor de los casos, es posible que tengamos que escanear la mitad del tamaño de la matriz (n / 2).

Por lo tanto, la búsqueda lineal se puede definir como la técnica que atraviesa la matriz secuencialmente para ubicar el elemento dado. El programa que se muestra a continuación ilustra la búsqueda de un elemento de la matriz mediante la búsqueda.

Eficiencia de búsqueda lineal

El consumo de tiempo o el número de comparaciones realizadas en la búsqueda de un registro en una tabla de búsqueda determina la eficacia de la técnica. Si el registro deseado está presente en la primera posición de la tabla de búsqueda, solo se realiza una comparación. Cuando el registro deseado es el último, entonces se deben hacer n comparaciones. Si el registro debe presentarse en algún lugar de la tabla de búsqueda, en promedio, el número de comparaciones será (n + 1/2). El peor de los casos de eficiencia de esta técnica es O (n) representa el orden de ejecución.

Programa C para buscar un elemento con técnica de búsqueda lineal.

#incluir #incluir void main () {int a, n, i, item, loc = -1; clrscr (); f (" nIntroduzca el número de elemento:"); scanf ("% d", & n); f ("Ingrese los números: n"); para (i = 0; i <= n-1; i ++) {scanf ("% d", & a); } f (" nIntroduzca el número a buscar:"); scanf ("% d", & item); para (i = 0; i <= n-1; i ++) {if (item == a) {loc = i; rotura; }} if (loc> = 0) {f (" n% d se encuentra en la posición% d:", item, loc + 1); } else {f (" n El artículo no existe"); } getch (); }

Definición de búsqueda binaria

La búsqueda binaria es un algoritmo extremadamente eficiente. Esta técnica de búsqueda consume menos tiempo en la búsqueda del elemento dado en las mínimas comparaciones posibles. Para hacer la búsqueda binaria, primero, tenemos que ordenar los elementos de la matriz.

La lógica detrás de esta técnica se da a continuación:

• Primero, encuentre el elemento medio de la matriz.
• El elemento central de la matriz se compara con el elemento a buscar.

Pueden surgir tres casos:

1. Si el elemento es el elemento requerido, entonces la búsqueda es exitosa.
2. Cuando el elemento es menor que el elemento deseado, busque solo la primera mitad de la matriz.
3. Si es mayor que el elemento deseado, busque en la segunda mitad de la matriz.

Repita los mismos pasos hasta que se encuentre un elemento o se agote en el área de búsqueda. En este algoritmo, cada vez que se reduce el área de búsqueda. Por lo tanto, el número de comparaciones es como máximo log (N + 1). Como resultado, es un algoritmo eficiente en comparación con la búsqueda lineal, pero la matriz tiene que ser ordenada antes de hacer la búsqueda binaria.

Programa C para encontrar un elemento con técnica de búsqueda binaria.

#incluir void main () {int i, beg, end, middle, n, search, array; f ("Ingrese el número de elemento n"); scanf ("% d", & n); f ("Ingrese los% d números n", n); para (i = 0; i <n; i ++) scanf ("% d", & array); f ("Ingrese el número a buscar n"); scanf ("% d", & búsqueda); rogar = 0; final = n - 1; medio = (inicio + final) / 2; while (beg <= end) {if (array <search) beg = middle + 1; de lo contrario if (array == search) {f ("La búsqueda fue exitosa. n% d encontrado en la ubicación% d. n", search, middle + 1); rotura; } else end = middle - 1; medio = (inicio + final) / 2; } if (beg> end) f ("¡La búsqueda no tiene éxito!% d no está presente en la lista. n", buscar); getch (); }

1. La búsqueda lineal es de naturaleza iterativa y utiliza un enfoque secuencial. Por otro lado, la búsqueda binaria implementa el enfoque de dividir y conquistar.
2. La complejidad temporal de la búsqueda lineal es O (N) mientras que la búsqueda binaria tiene O (log₂NORTE).
3. El mejor tiempo de caso en la búsqueda lineal es para el primer elemento, es decir, O (1). Por el contrario, en la búsqueda binaria, es para el elemento medio, es decir, O (1).
4. En la búsqueda lineal, el peor caso para buscar un elemento es N número de comparación. Por el contrario, es log₂N número de comparación para búsqueda binaria.
5. La búsqueda lineal se puede implementar tanto en una matriz como en una lista vinculada, mientras que la búsqueda binaria no se puede implementar directamente en la lista vinculada.
6. Como sabemos, la búsqueda binaria requiere la matriz ordenada, razón por la cual requiere procesamiento para insertar en su lugar adecuado para mantener una lista ordenada. Por el contrario, la búsqueda lineal no requiere elementos ordenados, por lo que los elementos se insertan fácilmente al final de la lista.
7. La búsqueda lineal es fácil de usar y no se necesitan elementos ordenados. Por otro lado, el algoritmo de búsqueda binaria es, sin embargo, complicado y los elementos están necesariamente ordenados.

Conclusión

Los algoritmos de búsqueda lineal y binaria pueden ser útiles según la aplicación. Cuando una matriz es la estructura de datos y los elementos se ordenan en orden, se prefiere la búsqueda binaria para rápidobuscando. Si la lista vinculada es la estructura de datos, independientemente de cómo estén organizados los elementos, se adopta la búsqueda lineal debido a la falta de disponibilidad de la implementación directa del algoritmo de búsqueda binaria.

El algoritmo de búsqueda binario típico no puede emplearse en una lista vinculada porque la lista vinculada es de naturaleza dinámica y no se sabe dónde se asigna realmente el elemento intermedio. Por lo tanto, existe un requisito para diseñar la variación del algoritmo de búsqueda binaria que también puede funcionar en la lista vinculada porque la búsqueda binaria es más rápida en ejecución que una búsqueda lineal.