in

Búsqueda lineal frente a búsqueda binaria

ds linear search vs binary search

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 que 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 simple.

Supongamos que tenemos una matriz de 10 elementos como se muestra en la siguiente figura:

Búsqueda lineal frente a búsqueda binaria

La figura anterior muestra una matriz de tipos de caracteres con 10 valores. Si queremos buscar ‘E’, entonces la búsqueda comienza desde el 0th element y escanea cada elemento hasta que no se encuentra el elemento, es decir, ‘E’. No podemos saltar directamente del 0th elemento al 4th elemento, 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 del medio 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 toma 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 una matriz ordenada como sin clasificar. El algoritmo de búsqueda binaria se basa en la técnica de dividir y conquistar, 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 a la 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 Derecha denota el elemento que se encuentra 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:

Búsqueda lineal frente a búsqueda binaria

El valor del elemento medio se puede calcular como:

Búsqueda lineal frente a búsqueda binaria

Por lo tanto, mid = 4 y a[mid] = 50. El elemento a buscar es 70, por lo que un[mid] no es igual a los datos. Se satisface el caso 2, es decir, datos> a[mid].

Búsqueda lineal frente a búsqueda binaria

Paso 2: Como datos> a[mid], por lo que 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:

Búsqueda lineal frente a búsqueda binaria

Ahora, nuevamente, el valor medio se calcula usando la fórmula anterior, y el valor de mid se convierte en 7. Ahora, el valor medio se puede representar como:

Búsqueda lineal frente a búsqueda binaria

En la figura anterior, podemos observar que un[mid]> datos, así que de nuevo, el valor de mid se calculará en el siguiente paso.

Paso 3: Como un[mid]> datos, el valor de right se reduce a mediados de-1. El valor de mid es 7, por lo que el valor de right se convierte en 6. La matriz se puede representar como:

Búsqueda lineal frente a búsqueda binaria

El valor de mid se calculará de nuevo. Los valores de izquierda y derecha son 5 y 6, respectivamente. Por lo tanto, el valor de mid es 5. Ahora el mid se puede representar en una matriz como se muestra a continuación:

Búsqueda lineal frente a búsqueda binaria

En la figura anterior, podemos observar que un[mid]

Paso 4: Como un[mid]

Ahora el valor de mid se calcula nuevamente usando la fórmula que ya hemos discutido. 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:

Búsqueda lineal frente a búsqueda binaria

Podemos observar en la figura anterior que un[mid]= datos. Por lo tanto, la búsqueda se completa y el elemento se encuentra correctamente.

Diferencias entre búsqueda lineal y búsqueda binaria

Búsqueda lineal frente a búsqueda binaria

Las siguientes son las diferencias entre la búsqueda lineal y la búsqueda binaria:

Descripción

La búsqueda lineal es una búsqueda que encuentra un elemento en la lista buscando el elemento secuencialmente hasta que el elemento se encuentra en la lista. Por otro lado, una búsqueda binaria es una búsqueda que encuentra el elemento intermedio en la lista de forma recursiva hasta que el elemento intermedio coincide con un elemento buscado.

Trabajo 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 elemento. Por otro lado, la búsqueda binaria divide la matriz por la mitad calculando el elemento medio de una matriz.

Implementación

La búsqueda lineal se puede implementar en cualquier estructura de datos lineal como vector, lista enlazada individualmente, 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 organizar en cualquier orden, mientras que en una búsqueda binaria, los elementos deben organizarse 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 por orden. Puede organizarse 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 dividir y conquistar.

Conjunto de datos

La búsqueda lineal no es adecuada para un gran conjunto de datos. Si queremos buscar el elemento, que es el último elemento de la matriz, una búsqueda lineal comenzará a buscar 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, ya que lleva 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 volvería 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 en matrices unidimensionales y multidimensionales, mientras que la búsqueda binaria solo se puede implementar en la matriz unidimensional.

Eficiencia

La búsqueda lineal es menos eficiente cuando consideramos los 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.

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 al encontrar el elemento medio de la matriz.
Datos ordenados En una búsqueda lineal, los elementos no necesitan estar ordenados. 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 los conjuntos de datos de pequeño tamaño. Es preferible para los 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 escenario para encontrar el elemento es O (log2norte).
En el mejor de los casos En una búsqueda lineal, el mejor escenario para encontrar el primer elemento de la lista es O (1). En una búsqueda binaria, el mejor escenario para encontrar el primer elemento de la lista es O (1).
Matriz dimensional Se puede implementar tanto en una matriz única como multidimensional. Solo se puede implementar en una matriz multidimensional.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

meQV3mj5UecNRr8LEUkJMW 1200 80

Cómo cambiar Google Chrome al modo oscuro

03kQk2hBUB7T0lg4K3EymJf 6.1634241457.fit lim.size 1200x630

Cómo convertir su teléfono inteligente en una cámara web inalámbrica