Antes de comprender las diferencias entre la búsqueda lineal y binaria, primero debemos conocer la búsqueda lineal y la búsqueda binaria por separado.
¿Qué es una búsqueda lineal?
Una búsqueda lineal también se conoce como búsqueda secuencial y simplemente escanea cada elemento a la vez. Supongamos que queremos buscar un elemento en una matriz o lista; simplemente calculamos su longitud y no saltamos sobre ningún elemento.
Consideremos un ejemplo sencillo.
Supongamos que tenemos una matriz de 10 elementos como se muestra en la siguiente figura:
La figura anterior muestra una matriz de tipos de caracteres que tiene 10 valores. Si queremos buscar 'E', entonces la búsqueda comienza desde el 0thelemento y escanea cada elemento hasta que no se encuentra el elemento, es decir, 'E'. No podemos saltar directamente desde el 0thelemento al 4thelemento, es decir, cada elemento se escanea uno por uno hasta que no se encuentra el elemento.
Complejidad de la búsqueda lineal
Como búsqueda lineal, escanea cada elemento uno por uno hasta que no se encuentra el elemento. Si aumenta el número de elementos, también aumenta el número de elementos a escanear. Podemos decir que el El tiempo necesario para buscar los elementos es proporcional al número de elementos. . Por lo tanto, la complejidad del peor de los casos es O(n)
¿Qué es una búsqueda binaria?
Una búsqueda binaria es una búsqueda en la que se calcula el elemento intermedio para comprobar si es más pequeño o más grande que el elemento que se va a buscar. La principal ventaja de utilizar la búsqueda binaria es que no escanea cada elemento de la lista. En lugar de escanear cada elemento, realiza la búsqueda en la mitad de la lista. Por lo tanto, la búsqueda binaria requiere menos tiempo para buscar un elemento en comparación con una búsqueda lineal.
El único requisito previo de la búsqueda binaria es que una matriz debe estar ordenada, mientras que la búsqueda lineal funciona tanto en matrices ordenadas como sin clasificar. El algoritmo de búsqueda binaria se basa en la técnica de divide y vencerás, lo que significa que dividirá la matriz de forma recursiva.
Hay tres casos utilizados en la búsqueda binaria:
Caso 1: datos
Caso 2: datos>a[mid] luego derecha=mid-1
Caso 3: datos = a[mid] // se encuentra el elemento
En el caso anterior, ' a ' es el nombre de la matriz, medio es el índice del elemento calculado de forma recursiva, datos es el elemento que se va a buscar, izquierda denota el elemento izquierdo de la matriz y bien denota el elemento que ocurre en el lado derecho de la matriz.
Entendamos el funcionamiento de la búsqueda binaria a través de un ejemplo.
Supongamos que tenemos una matriz de tamaño 10 que está indexada de 0 a 9 como se muestra en la siguiente figura:
Queremos buscar 70 elementos de la matriz anterior.
Paso 1: Primero, calculamos el elemento medio de una matriz. Consideramos dos variables, es decir, izquierda y derecha. Inicialmente, izquierda = 0 y derecha = 9 como se muestra en la siguiente figura:
El valor del elemento medio se puede calcular como:
Por lo tanto, mid = 4 y a[mid] = 50. El elemento a buscar es 70, por lo que a[mid] no es igual a datos. Se cumple el caso 2, es decir, datos>a[mid].
Paso 2: Como datos>a[mid], el valor de left se incrementa en mid+1, es decir, left=mid+1. El valor de mid es 4, por lo que el valor de left se convierte en 5. Ahora, tenemos un subarreglo como se muestra en la siguiente figura:
Ahora nuevamente, el valor medio se calcula usando la fórmula anterior, y el valor medio se convierte en 7. Ahora, el valor medio se puede representar como:
En la figura anterior, podemos observar que a[mid]>datos, por lo que nuevamente, el valor de mid se calculará en el siguiente paso.
Paso 3: Como dato[mid]>, el valor de right se reduce a mitad de 1. El valor de mid es 7, por lo que el valor de right pasa a ser 6. La matriz se puede representar como:
El valor de mid se calculará nuevamente. Los valores de izquierda y derecha son 5 y 6, respectivamente. Por lo tanto, el valor de mid es 5. Ahora mid se puede representar en una matriz como se muestra a continuación:
En la figura anterior, podemos observar que a[mid]
Etapa 4: Como[mediados] Ahora el valor de mid se calcula nuevamente usando la fórmula que ya hemos comentado. Los valores de izquierda y derecha son 6 y 6 respectivamente, por lo que el valor de mid se convierte en 6 como se muestra en la siguiente figura: Podemos observar en la figura anterior que a[mid]=data. Por lo tanto, la búsqueda se completa y el elemento se encuentra exitosamente. Las siguientes son las diferencias entre búsqueda lineal y búsqueda binaria: Descripción La búsqueda lineal es una búsqueda que encuentra un elemento en la lista buscándolo secuencialmente hasta que se encuentra el elemento en la lista. Por otro lado, una búsqueda binaria es una búsqueda que encuentra el elemento del medio en la lista de forma recursiva hasta que el elemento del medio coincide con un elemento buscado. Funcionamiento de ambas búsquedas. La búsqueda lineal comienza a buscar desde el primer elemento y escanea un elemento a la vez sin saltar al siguiente. Por otro lado, la búsqueda binaria divide la matriz por la mitad calculando el elemento central de la matriz. Implementación La búsqueda lineal se puede implementar en cualquier estructura de datos lineal, como un vector, una lista enlazada individualmente o una lista enlazada doble. Por el contrario, la búsqueda binaria se puede implementar en aquellas estructuras de datos con recorrido bidireccional, es decir, recorrido hacia adelante y hacia atrás. Complejidad La búsqueda lineal es fácil de usar, o podemos decir que es menos compleja ya que los elementos para una búsqueda lineal se pueden ordenar en cualquier orden, mientras que en una búsqueda binaria, los elementos deben ordenarse en un orden particular. Elementos ordenados Los elementos para una búsqueda lineal se pueden organizar en orden aleatorio. No es obligatorio en la búsqueda lineal que los elementos estén ordenados. Por otro lado, en una búsqueda binaria, los elementos deben estar ordenados. Se puede organizar en orden creciente o decreciente y, en consecuencia, se cambiará el algoritmo. Como la búsqueda binaria utiliza una matriz ordenada, es necesario insertar el elemento en el lugar adecuado. Por el contrario, la búsqueda lineal no necesita una matriz ordenada, por lo que el nuevo elemento se puede insertar fácilmente al final de la matriz. Acercarse La búsqueda lineal utiliza un enfoque iterativo para encontrar el elemento, por lo que también se conoce como enfoque secuencial. Por el contrario, la búsqueda binaria calcula el elemento medio de la matriz, por lo que utiliza el enfoque de divide y vencerás. conjunto de datos La búsqueda lineal no es adecuada para conjuntos de datos grandes. Si queremos buscar el elemento, que es el último elemento de la matriz, una búsqueda lineal comenzará desde el primer elemento y continuará hasta el último elemento, por lo que el tiempo necesario para buscar el elemento sería grande. Por otro lado, la búsqueda binaria es adecuada para un gran conjunto de datos porque requiere menos tiempo. Velocidad Si el conjunto de datos es grande en la búsqueda lineal, entonces el costo computacional sería alto y la velocidad se vuelve lenta. Si el conjunto de datos es grande en la búsqueda binaria, entonces el costo computacional sería menor en comparación con una búsqueda lineal y la velocidad se vuelve rápida. Dimensiones La búsqueda lineal se puede utilizar tanto en matrices unidimensionales como multidimensionales, mientras que la búsqueda binaria solo se puede implementar en matrices unidimensionales. Eficiencia La búsqueda lineal es menos eficiente cuando consideramos grandes conjuntos de datos. La búsqueda binaria es más eficiente que la búsqueda lineal en el caso de grandes conjuntos de datos. Veamos las diferencias en forma tabular. 
Diferencias entre búsqueda lineal y búsqueda binaria
foreach mecanografiado
Base de comparación búsqueda lineal Búsqueda binaria Definición La búsqueda lineal comienza a buscar desde el primer elemento y compara cada elemento con un elemento buscado hasta que no se encuentra el elemento. Encuentra la posición del elemento buscado encontrando el elemento central de la matriz. datos ordenados En una búsqueda lineal, no es necesario organizar los elementos en orden. La condición previa para la búsqueda binaria es que los elementos deben estar ordenados. Implementación La búsqueda lineal se puede implementar en cualquier estructura de datos lineal, como una matriz, una lista vinculada, etc. La implementación de la búsqueda binaria es limitada ya que solo se puede implementar en aquellas estructuras de datos que tienen un recorrido bidireccional. Acercarse Se basa en el enfoque secuencial. Se basa en el enfoque de divide y vencerás. Tamaño Es preferible para conjuntos de datos de tamaño pequeño. Es preferible para conjuntos de datos de gran tamaño. Eficiencia Es menos eficiente en el caso de conjuntos de datos de gran tamaño. Es más eficiente en el caso de conjuntos de datos de gran tamaño. Peor de los casos En una búsqueda lineal, el peor escenario para encontrar el elemento es O(n). En una búsqueda binaria, el peor de los casos para encontrar el elemento es O(log2norte). En el mejor de los casos En una búsqueda lineal, el mejor de los casos para encontrar el primer elemento de la lista es O(1). En una búsqueda binaria, el mejor de los casos para encontrar el primer elemento de la lista es O(1). Matriz dimensional Se puede implementar tanto en una matriz unidimensional como multidimensional. Sólo se puede implementar en una matriz multidimensional.