La principal diferencia entre la búsqueda lineal y la búsqueda binaria es que la búsqueda binaria requiere menos tiempo para 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 ordenarse mientras que en la búsqueda lineal no hay tal requisito previo. Aunque ambos métodos de búsqueda utilizan diferentes técnicas que se discuten a continuación.
Gráfica comparativa
| Bases para la comparación | Busqueda lineal | Búsqueda binaria |
|---|---|---|
| Complejidad del tiempo | EN) | O (log 2 N) |
| Mejor tiempo de 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 | Se puede concluir después de solo 2 N comparaciones de registro |
| Puede ser implementado en | Array y lista enlazada | No se puede implementar directamente en la lista enlazada |
| Operación de inserción | Se inserta fácilmente al final de la lista | Requieren que el procesamiento se inserte en su lugar adecuado para mantener una lista ordenada |
| Tipo de algoritmo | Iterativo en la naturaleza | Divide y conquista en la naturaleza. |
| Utilidad | Fácil de usar y sin necesidad de elementos ordenados. | De todos modos, los algoritmos y elementos complicados 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 verifica si es un 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, el número de un caso promedio puede 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 de forma secuencial para localizar el elemento dado. El programa que se presenta 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 eficiencia de la técnica. Si el registro deseado está presente en la primera posición de la tabla de búsqueda, entonces solo se hace una comparación. Cuando el registro deseado es el último, entonces se deben hacer n comparaciones. Si el registro se presenta en algún lugar de la tabla de búsqueda, en promedio, el número de comparaciones será (n + 1/2). El peor caso de eficiencia de esta técnica es que O (n) representa el orden de ejecución.
C Programa para buscar un elemento con técnica de búsqueda lineal.
#include #include void main () {int a [100], n, i, item, loc = -1; clrscr (); printf ("\ nIntroduzca el número de elemento:"); scanf ("% d", & n); printf ("Ingrese los números: \ n"); para (i = 0; i <= n-1; i ++) {scanf ("% d", & a [i]); } printf ("\ nIntroduzca el número a buscar:"); scanf ("% d", & item); para (i = 0; i = 0) {printf ("\ n% d se encuentra en la posición% d:", elemento, loc + 1); } else {printf ("\ 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 comparaciones mínimas 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, encuentra el elemento central de la matriz.
- El elemento central de la matriz se compara con el elemento a buscar.
Hay tres casos que podrían surgir:
- Si el elemento es el elemento requerido, entonces la búsqueda es exitosa.
- Cuando el elemento sea menor que el elemento deseado, busque solo la primera mitad de la matriz.
- 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 debe ordenarse antes de realizar la búsqueda binaria.
C Programa para encontrar un elemento con técnica de búsqueda binaria.
#include void main () {int i, beg, end, middle, n, search, array [100]; printf ("Introduzca el número del elemento \ n"); scanf ("% d", & n); printf ("Ingrese los% d números \ n", n); para (i = 0; i <n; i ++) scanf ("% d", & array [i]); printf ("Introduzca el número a buscar \ n"); scanf ("% d", & buscar); beg = 0; end = n - 1; medio = (beg + fin) / 2; while (beg <= end) {if (array [middle] end) printf ("¡La búsqueda no tuvo éxito!% d no está presente en la lista. \ n", buscar); getch (); } Diferencias clave entre la búsqueda lineal y la búsqueda binaria
- 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.
- La complejidad temporal de la búsqueda lineal es O (N), mientras que la búsqueda binaria tiene O (log 2 N).
- El mejor tiempo de caso en la búsqueda lineal es para el primer elemento, es decir, O (1). En contra, en la búsqueda binaria, es para el elemento central, es decir, O (1).
- En la búsqueda lineal, el caso más desfavorable para buscar un elemento es el número N de comparación. Por el contrario, es el número log 2 N de comparación para la búsqueda binaria.
- La búsqueda lineal se puede implementar en una matriz, así como en la lista vinculada, mientras que la búsqueda binaria no se puede implementar directamente en la lista vinculada.
- Como sabemos, la búsqueda binaria requiere la matriz ordenada que es la razón por la que requiere un proceso de inserción 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.
- La búsqueda lineal es fácil de usar, y no hay necesidad de ningún elemento ordenado. Por otro lado, el algoritmo de búsqueda binario es, sin embargo, complicado, y los elementos están necesariamente ordenados en orden.
Conclusión
Tanto los algoritmos de búsqueda lineal como los binarios pueden ser útiles dependiendo de la aplicación. Cuando una matriz es la estructura de datos y los elementos están ordenados en orden, se prefiere la búsqueda binaria para una búsqueda rápida . Si la lista vinculada es la estructura de datos, independientemente de cómo se organizan 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 la lista enlazada porque la lista enlazada es de naturaleza dinámica y no se sabe dónde se asigna realmente el elemento central. Por lo tanto, hay un requisito para diseñar la variación del algoritmo de búsqueda binaria que puede funcionar en la lista enlazada también porque la búsqueda binaria es más rápida en ejecución que una búsqueda lineal.
