¿Cuál es mejor, búsqueda binaria o búsqueda lineal?

Una búsqueda lineal escanea un elemento a la vez, sin saltar a ningún elemento.

1. La peor complejidad del caso es O (n), a veces conocida como búsqueda O (n)
2. El tiempo necesario para buscar elementos sigue aumentando a medida que aumenta el número de elementos.

Sin embargo, una búsqueda binaria reduce su búsqueda a la mitad tan pronto como encuentre el medio de una lista ordenada.

1. Se busca el elemento del medio para verificar si es mayor o menor que el valor a buscar.
2. En consecuencia, la búsqueda se realiza en la mitad de la lista dada

Diferencias importantes

• Los datos de entrada deben ordenarse en Búsqueda binaria y no en Búsqueda lineal
• La búsqueda lineal realiza el acceso secuencial mientras que la búsqueda binaria accede a los datos aleatoriamente.
• Complejidad de tiempo de búsqueda lineal -O (n), la búsqueda binaria tiene complejidad de tiempo O (log n).
• La búsqueda lineal realiza comparaciones de igualdad y la búsqueda binaria realiza comparaciones de orden

Veamos un ejemplo para comparar los dos:

0.1. Búsqueda lineal para encontrar el elemento “J” en una lista ordenada dada de AX

0.2. Búsqueda binaria para encontrar el elemento “J” en una lista ordenada dada de AX

Obviamente, la búsqueda binaria es mejor que la búsqueda lineal . la búsqueda binaria funciona en O (logn) y la búsqueda lineal funciona en O (n). No voy a entrar en detalles técnicos, ya que puede encontrarlo en cualquier lugar. Solo voy a dar una analogía con el escenario de la vida diaria para que pueda tener una buena comprensión de la complejidad del tiempo.

Suponga que está hablando con una niña / niño, a quien le gusta más en WhatsApp pero que él / ella responde muy recientemente. Entonces, cómo te sientes en ese momento te sientes frustrado. lo que quieras tan pronto como le envíes un mensaje de texto. él / ella debe responder de inmediato.

así que eso también sucede en la aplicación del mundo real. suponga que tiene miles de millones de registros y desea buscar un registro en particular para obtener el resultado tan pronto como ingrese su consulta. no quieres esperar porque esperar es frustrante.

EDITAR: Aquí estoy considerando que los datos de entrada ya están ordenados. y mi motivo principal para responder a esta pregunta es dar sentido a la importancia de un algoritmo eficiente en el mundo real.

Tengo una gran idea. Hagamos una competencia.

Así que aquí va. Elija un diccionario, no un diccionario en línea de corazón débil, una copia física. Elija una palabra al azar, por ejemplo, conocimiento .

Ahora, la competencia es simple: encuentre el conocimiento lo más rápido posible. Buscará secuencialmente, comenzando con la página 1, la página 2, la página 3, y así sucesivamente, hasta que encuentre conocimiento .

Haré una búsqueda binaria y abriré el libro cerca del medio, veré qué palabras tiene y buscaré conocimiento en la mitad correcta. Cada vez, limitaré la búsqueda reduciendo a la mitad el número de páginas.

Estoy seguro de que ir en secuencia será mucho más rápido para el diccionario de 8 páginas, pero para 30 páginas o más, la búsqueda binaria ganará.

La búsqueda binaria requiere comparaciones [math] \ lceil \ log_2 (número \ de \ páginas) \ rceil [/ math], mientras que la búsqueda lineal requiere comparaciones de número de páginas

La búsqueda binaria supone dos cosas:

1. Que la lista de artículos está ordenada.
2. El acceso aleatorio a cualquier índice de elemento es una operación O (1).

Una matriz ordenada generalmente cumple con estos requisitos.

Con una búsqueda lineal, si el artículo que está buscando es el último en el contenedor, o no está en el contenedor, deberá verificar cada elemento en el contenedor antes de tomar esa determinación. Eso lo convierte en un algoritmo O (N) basado en el peor de los casos.

La búsqueda binaria es más eficiente que una búsqueda lineal, porque divide recursivamente el espacio del problema por la mitad, descartando la mitad de los elementos restantes con cada salto, convirtiéndolo en un algoritmo O (log N).

La búsqueda binaria salta al elemento del medio en el contenedor y observa cómo el elemento que está buscando se compara con ese elemento del medio. Entonces hay 3 casos posibles:

1. El elemento central es el elemento que está buscando: la búsqueda ha finalizado.
2. El elemento que está buscando debe ubicarse antes en el contenedor que el elemento central (si está allí). En ese caso, todo lo que viene después del elemento del medio puede ignorarse a los fines de la búsqueda.
3. El elemento que está buscando debe aparecer después del elemento del medio. En ese caso, todo lo que viene antes del elemento del medio puede ignorarse a los fines de la búsqueda.

El algoritmo se repite según sea necesario, dividiendo el espacio de búsqueda por la mitad cada vez hasta que encuentra el elemento o el espacio de búsqueda se reduce hasta el punto de que no quedan elementos para inspeccionar.

Como puede ver, descarta muchos elementos muy rápidamente, por lo que no es necesario verificarlos, y eso es lo que lo hace más rápido que una búsqueda lineal.

Muchas gracias por preguntarme y también, mis disculpas por la lenta respuesta,

Una búsqueda lineal escanea un elemento a la vez, sin saltar a ningún elemento.

1. La peor complejidad del caso es O (n), a veces conocida como búsqueda O (n)
2. El tiempo necesario para buscar elementos sigue aumentando a medida que aumenta el número de elementos.

Sin embargo, una búsqueda binaria reduce su búsqueda a la mitad tan pronto como encuentre el medio de una lista ordenada.

1. Se busca el elemento del medio para verificar si es mayor o menor que el valor a buscar.
2. En consecuencia, la búsqueda se realiza en la mitad de la lista dada

• Otras diferencias importantes

En general, BynarySearch. Por qué ? porque siempre dividiremos tu trabajo por la mitad. Pero para eso necesitarás un conjunto ordenado (también conocido como matriz ordenada).

Con la búsqueda lineal, debe pasar por todos los elementos, digamos que tiene 1,000,000 de elementos, por lo que debe buscar a través de 1,000,000 de elementos, porque lo que sea que esté buscando puede ubicarse en cualquier lugar. Pero, usando la búsqueda binaria, solo tiene que golpear 20 veces (log n) aproximadamente.

¡Conoce tus complejidades!

La búsqueda binaria produce una eficiencia O (log n), debido al enfoque de “cortar” y reducir a la mitad el conjunto de datos. Crece menos, en términos de pérdida de velocidad, en conjuntos de datos más grandes.

La búsqueda lineal, puede ser, en aras del argumento (no del todo exacto) dicho, que es O (n), lo que significa que se escala peor, en conjuntos más grandes.

Sin embargo, los dos requieren permutaciones diferentes.

Binario requiere que los datos de entrada se ordenen; no es lineal.

Binario lo hace ordenando, lineal lo hace por igualdad.

Lineal, como se discutió, es lineal, lo que significa que pasa por 1–10, mientras que, binario, salta.

Es relativo a la situación, por lo tanto.

La mejor de las suertes.

Entre la búsqueda lineal y binaria, por supuesto, la búsqueda binaria es mejor ya que le da una complejidad de tiempo de tiempo de búsqueda de O (logn), por otro lado, la búsqueda lineal le da tiempo de búsqueda de O (n). En la búsqueda binaria donde la entrada tiene que ser ordenada, en realidad no atravesamos toda la matriz a la que vamos dividiendo n, luego n / 2 y así sucesivamente. Pero en la búsqueda lineal, en realidad podemos terminar de buscar la matriz completa en el peor de los casos, en el caso promedio O (n / 2) = O (n).

Pero si compara la búsqueda de interpolación con la búsqueda binaria, entonces la búsqueda de interpolación es aún mejor que la búsqueda binaria. Búsqueda de interpolación: un algoritmo de búsqueda mejor que la búsqueda binaria

Creo que depende del tipo de entrada donde necesita buscar.

La búsqueda binaria es mejor y bastante rápida … ya que la complejidad del tiempo será O (log n). Como siempre divide el tamaño de entrada a la mitad y la mitad … pero sí, la entrada debe estar ordenada … o en alguna secuencia …

Para la búsqueda lineal, debe analizar la lista de entrada completa … por lo que la complejidad será O (n). Pero sí, en esto no debe preocuparse si la entrada es secuencial o no …

Hoy en día puede crear muchos otros algoritmos solo para reducir la complejidad del tiempo en función de sus necesidades y aportes.

Espero que esto ayude.

La búsqueda binaria es definitivamente mejor si la matriz dada ya está ordenada; de lo contrario, es recomendable ordenar la matriz y luego usar la búsqueda binaria para ir hacia la búsqueda lineal.

En serach lineal, cuando realiza una operación, reduce el tamaño del problema en uno. Pero cuando realiza una operación en búsqueda binaria, reduce el tamaño del problema a la mitad. Suena eficiente, ¿no?

Nota: el serach binario se aplica solo en matrices ordenadas.

Respondí esta pregunta asumiendo que ya has leído teoría y algoritmos de búsqueda lineal y binaria.

La búsqueda binaria se llama dividir y conquistar búsqueda. Tenemos que encontrar el elemento medio y luego ver si el elemento que queremos buscar es menor que el valor medio o mayor que el valor medio. Por lo tanto, cada vez que el número de iteraciones se divide por 2. Por lo tanto, podemos buscar el elemento en el peor de los casos en las iteraciones (log n a base 2) donde n es el número de elementos.

Para la búsqueda lineal tenemos que ir desde el principio hasta el final. Entonces, la peor complejidad del caso es n.

Entonces la búsqueda binaria es eficiente. Se debe seguir una condición para que podamos usar la búsqueda binaria, es decir, se debe ordenar la matriz de elementos, entonces solo podemos usar la búsqueda binaria. Tampoco podemos usar la búsqueda binaria en la implementación de la lista vinculada.

Un ejemplo de eficiencia de búsqueda binaria es que si tenemos 1024 elementos, el elemento que se encuentra está en la posición 1024

En 10 iteraciones podemos encontrar el elemento usando búsqueda binaria y en 1024 iteraciones usando búsqueda lineal.

La búsqueda binaria es una solución mucho mejor, ya que el costo de la clasificación solo se establecerá una vez, pero la búsqueda lineal siempre tomará un tiempo lineal. Si los elementos ya están ordenados, la búsqueda binaria sería la mejor opción, de lo contrario, debe considerar la cantidad de búsquedas.

Depende

Si la lista es “corta”, no importa la eficiencia, elija lineal porque hace que el código sea más limpio.

Si la lista es “larga” y ordenada, búsqueda binaria.

Si la lista es “larga” y no está ordenada, depende de cuántas búsquedas tenga que hacer. También depende exactamente de cuáles son los datos. Y qué tan lejos está de ordenado si está usando un tipo que puede aprovechar eso. En general, muchas búsquedas: ordénelo luego búsqueda binaria, no muchas búsquedas: búsqueda lineal. Saber dónde está la línea cuando hacer el cambio es complicado.

Y el límite entre “corto” y “largo” también es un poco confuso.

Y a todos ustedes que respondieron definitivamente a la búsqueda binaria, ¿en serio? Ven ahora…

Depende de la entrada.

Búsqueda lineal:

Independientemente del orden de entrada, la búsqueda lineal encontrará el elemento en O (n).

Búsqueda binaria :

Si la entrada está ordenada, la búsqueda binaria encontrará el elemento en O (log n), que es mucho más rápido que la búsqueda lineal.

Si la entrada no está ordenada, tomará:

Ordenar O (n log n) + Búsqueda binaria O (log n) = n log n.

Conclusión

Si la entrada está ordenada, la búsqueda binaria es el camino a seguir.

Depende de la entrada. Si el conjunto ya está ordenado, la búsqueda binaria funciona bien en O (log n). Si el conjunto no está ordenado, puede realizar una búsqueda lineal que funciona en O (n)

Bueno depende de lo que quieras decir con mejor.

Solo puede aplicar la búsqueda binaria si la matriz sigue un orden; de lo contrario, la búsqueda lineal es la única opción. La búsqueda binaria se ejecuta en tiempo de registro, por lo que es más rápido que la búsqueda lineal, que lleva n tiempo. Si el tiempo no es una restricción, la búsqueda lineal es más fácil de implementar que la búsqueda binaria.