¿Por qué la búsqueda binaria, que necesita datos ordenados, se considera mejor que la búsqueda lineal?

Siempre he escuchado que la búsqueda lineal es un enfoque ingenuo y que la búsqueda binaria es mejor que en rendimiento debido a una mejor complejidad asintótica. Pero nunca entendí por qué es mejor que la búsqueda lineal cuando se requiere ordenar antes de la búsqueda binaria.

La búsqueda lineal es O(n)y la búsqueda binaria es O(log n). Esa parece ser la base para decir que la búsqueda binaria es mejor. Pero la búsqueda binaria requiere una clasificación que es O(n log n)para los mejores algoritmos. Por lo tanto, la búsqueda binaria no debería ser realmente más rápida, ya que requiere ordenación.

Estoy leyendo CLRS en el que el autor implica que en el orden de inserción en lugar de utilizar el enfoque de búsqueda lineal ingenuo, es mejor utilizar la búsqueda binaria para encontrar el lugar donde se debe insertar el elemento. En este caso, esto parece estar justificado, ya que en cada iteración de bucle hay una lista ordenada sobre la cual se puede aplicar la búsqueda binaria. Pero en el caso general en el que no hay garantía sobre el conjunto de datos en el que necesitamos buscar, ¿no está usando la búsqueda binaria en realidad peor que la búsqueda lineal debido a los requisitos de clasificación?

¿Hay algunas consideraciones prácticas que estoy pasando por alto que hacen que la búsqueda binaria sea mejor que la búsqueda lineal? ¿O la búsqueda binaria se considera mejor que la búsqueda lineal sin considerar el tiempo de cálculo requerido para la clasificación?

¿Hay algunas consideraciones prácticas que estoy pasando por alto que hacen que la búsqueda binaria sea mejor que la búsqueda lineal?

Sí, debe hacer la clasificación O (n log n) solo una vez, y luego puede hacer la búsqueda binaria O (log n) con la frecuencia que desee, mientras que la búsqueda lineal es O (n) cada vez.

Por supuesto, esto es solo una ventaja si realmente realiza múltiples búsquedas en los mismos datos. Pero los escenarios de "escribir una vez, leer a menudo" son bastante comunes.

La suposición básica es que no realiza una búsqueda.

Entonces, si necesita buscar los mismos datos varias veces, solo tiene que ordenar una vez y puede beneficiarse de la búsqueda binaria.

Si busca con frecuencia y tiene datos cambiantes, vale la pena usar una lista ordenada donde las nuevas entradas se ordenan en la lista.

Básicamente, la búsqueda binaria es mejor cuando busca la misma lista varias veces sin necesidad de recurrir.

Cuando necesita ordenar cada vez antes de buscar, no hay ninguna ventaja.

Tenga en cuenta que hay algoritmos de clasificación que son muy rápidos cuando la lista ya está ordenada (o casi ordenada). La mayoría de las determinaciones de rendimiento esperan una lista sin clasificar.

porque una vez que tiene una lista ordenada, no necesita volver a ordenarla cada vez, lo que significa que si tiene más de O (log n), la búsqueda por adelantado le dará una ganancia ( O(n log n + k log n)vsO(k*n)

Imagina dos guías telefónicas.

Una guía telefónica tiene los nombres en orden alfabético. Para encontrar la entrada que desea, abra en el medio, verifique la entrada y luego avance o retroceda dependiendo de si se sobrepasó o no.

La otra guía telefónica tiene los nombres en orden aleatorio. Para encontrar la entrada que desea, comience desde el principio y continúe hasta encontrar lo que desea.

¿Funcionará el segundo libro en cualquier ciudad de tamaño razonable?

Creo que el valor de la búsqueda binaria sobre la búsqueda lineal es contextual. Si comienza con un enorme conjunto de datos desordenados y solo planea extraer una pequeña cantidad de elementos de él, entonces ordenar y realizar una búsqueda binaria será lento. Sin embargo, si mantiene una lista ordenada durante toda la vida útil de su aplicación y accede a ella regularmente, entonces la búsqueda binaria es una mejor manera de hacerlo.

Como muchos otros han respondido, la búsqueda binaria es preferible porque el paso de clasificación se puede hacer solo una vez y la búsqueda real se puede hacer tantas veces como desee. Sin embargo, para ciertos valores de n (es decir, ciertos tamaños de entrada), la búsqueda binaria siempre es más eficaz que la búsqueda lineal (incluso para una sola ejecución).

El "punto de inflexión" se calcula resolviendo la ecuación de complejidad asintótica:

n log n + log n = n

Como puede ver en Wolfram Alpha, hay un valor numérico para n que garantiza que la búsqueda y clasificación binarias siempre sea más rápida que la búsqueda lineal sola. Por supuesto, el valor real de n que funciona en su caso depende de muchos factores que pueden ser difíciles de estimar.

De acuerdo con este interesante artículo de Mark Probst, que incluye algunas buenas mediciones de rendimiento en profundidad en los procesadores actuales:

Si necesita buscar a través de una matriz ordenada de enteros y el rendimiento es muy, muy importante, use la búsqueda lineal si su matriz está por debajo de alrededor de 64 elementos de tamaño, busque binaria si está por encima.

En palabras simples:

Si tiene una lista desordenada con diez mil millones de artículos, y el artículo que está buscando es el último, terminará leyendo los diez mil millones de artículos.

En el caso de la búsqueda binaria, la indexación se puede realizar solo una vez. Las inserciones posteriores se pueden realizar en el lugar correcto para mantener el orden.

Si bien ya se han enumerado muchas buenas razones para "la búsqueda binaria es mejor", también podemos echar un vistazo a las ventajas desde la perspectiva del usuario:

Si bien normalmente puede vivir muy bien con el pequeño tiempo de espera dividido entre las acciones de ingreso de datos cuando realiza una inserción ordenada, desea que la "búsqueda" sea lo más rápida posible. Desde el punto de vista del usuario, la inserción ordenada combinada con una búsqueda binaria brinda la mejor experiencia de usuario posible.