Búsqueda binaria

Question

Entonces, quiero entender más sobre la búsqueda binaria, porque realmente no entiendo. La búsqueda binaria requiere una condición previa que se ordene una matriz. Lo tengo bien? Parece que un método debería verificar esta condición previa y lanzar una excepción si no se cumple. Pero, ¿por qué verificar la condición previa es una mala idea?

Answer 1

Es una mala idea porque verificar los datos se ordena toma tomas n pasos. Toda la búsqueda es sobre log(n) pasos.
Si vas a verificar, también podrías hacer una búsqueda lineal.

Answer 2

El objetivo de una búsqueda binaria es que, dado que los datos ya están ordenados, puede localizar rápidamente la información que desea.

Tome la guía telefónica, que se clasifica por apellido.

¿Cómo encuentras a alguien en la guía telefónica? Lo abre a una página que supone que estará cerca de lo que desea, y luego comienzas a voltear páginas.

Pero no volteas una página cada vez, si te perdiste por mucho, volteas un montón de páginas, y finalmente comienzas a voltear una a la vez, hasta que finalmente comiences a mirar una sola página.

Esto es lo que hace la búsqueda binaria. Dado que los datos están ordenados, sabe que puede omitir mucho y hacer otro aspecto, y se centrará en la información que desee.

Una búsqueda binaria hace 1 comparación para cada número duplicado de elementos. Por lo tanto, una colección de elementos 1024 requeriría alrededor de 10 comparaciones, como máximo, para encontrar su información, o al menos descubrir que no está allí.

Si usted, antes de ejecutar la búsqueda binaria real, realiza una ejecución completa para verificar si los datos están ordenados, también podría escanear la información. Una ejecución completa + la búsqueda binaria requerirá operaciones N + log2 N, por lo que para 1024 elementos, requeriría alrededor de 1034 comparaciones, mientras que un escaneo simple para la información requerirá la mitad, que es 512.

Entonces, si no puede garantizar que los datos se ordenen, no debe usar la búsqueda binaria, ya que será superado por un escaneo simple.

---

Editar: Sin embargo, diré esto, podría agregar un paso de código de depuración para verificar esto, para atrapar errores en el código que se supone que prepara los datos para la búsqueda binaria, pero sepa que, debido a lo que he escrito anteriormente, Esto hará que el tiempo de ejecución total sea mucho más alto, por lo que dependiendo de lo que desee hacer con este cheque, puede o no querer agregarlo. Pero no debe estar presente en el código de lanzamiento.

Answer 3

Sí, una búsqueda binaria implica 0 (log n) pasos y verificar la secuencia completa está ordenada implica 0 (n) pasos. Desde mi punto de vista, es bueno verificarlo en modo de depuración, no durante el lanzamiento.

Answer 4

Búsqueda binaria asume que los datos de entrada están ordenados. Así que aquí tienes razón.

Ahora, en general, verifica si los datos se clasifican en algún momento. Por lo tanto, ejecutar esto antes de cada búsqueda haría que la búsqueda sea realmente ineficiente.

Más detalles.

Suponga que 'n' es la cantidad de sus datos.

Búsqueda binaria necesidades O(log(n)) operación en el peor de los casos para encontrar un elemento. Asegurarse de que se ordenen los datos requiere O(n) operaciones.

Entonces, si verificamos la condición previa cada vez para mucho n Comenzaremos a pasar la mayor parte del tiempo para verificar la condición previa que hacer una búsqueda real.

Y no es tan difícil decir cuándo verá tal efecto. Acabo de calcular cuánto tiempo pasará en la búsqueda previa frente a la búsqueda real.

• Por 1 elemento no pasas tiempo buscando.
• Para 2 elementos gastas 50% en la búsqueda.
• Para 5 elementos gastas 46% en buscar
• Para 20 elementos gastas un 22% en la búsqueda.
• Para 100 elementos gastas un 7% en la búsqueda.

Y así. En todos los casos, el descanso en el tiempo se gasta en la verificación de condición previa.

Answer 5

Además de lo que todos los demás dijeron sobre el tiempo de ejecución (o (n) para verificar todos los elementos, vs. o (log (n)) para ejecutar búsqueda binaria).

Creo que estás malinterpretando la idea de una condición previa. Las condiciones previas y las post-condiciones son un contrato. Si su condición previa es verdadera y ejecuta su algoritmo, entonces su condición de publicación será cierta. Si su condición previa es falsa, entonces no garantiza la condición posterior.

Básicamente, Binary Search dice esto: si los datos que me das ya están ordenados, entonces puedo decirle la posición de un dato específico, o si no está presente, realizando aproximadamente las comprobaciones de registro (n). Si los datos no están ordenados, no garantizo mi respuesta.

El trabajo que lo lleva de su pre-condición a su post-condición si su algoritmo. En este caso, búsqueda binaria.

Answer 6

La pregunta original presupone que está utilizando una búsqueda binaria en una colección de datos. Ese no es siempre el caso. Muchas veces solo estás tratando de calcular un número en algún intervalo.

Supongamos que está tratando de calcular la configuración de velocidad óptima para un ventilador. Por alguna razón, no puede encontrar una expresión de forma cerrada, por lo que simula el flujo de aire a diferentes configuraciones de velocidad.

Suponiendo que el ventilador puede funcionar a cualquier velocidad de 0 rpm a 5000 rpm, en realidad no tiene que generar una lista de velocidades posibles. Simplemente encuentre el promedio del mínimo y máximo anterior en cada paso de la búsqueda binaria.