Búsqueda binaria
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la
versión revisada el 20 de marzo de 2021; las comprobaciones requieren
29 ediciones .
La búsqueda binaria (binaria) (también conocida como método de bisección o dicotomía ) es un algoritmo clásico para encontrar un elemento en una matriz ordenada (vector) que utiliza la división de la matriz en mitades. Se utiliza en informática , matemáticas computacionales y programación matemática .
Un caso especial de búsqueda binaria es el método de bisección , que se usa para encontrar las raíces de una función continua dada en un intervalo dado.
Encontrar un elemento en una matriz ordenada
- Determinar el valor de un elemento en medio de una estructura de datos. El valor resultante se compara con la clave.
- Si la clave es menor que el valor medio, la búsqueda se realiza en la primera mitad de los elementos, de lo contrario, en la segunda.
- La búsqueda se reduce al hecho de que el valor del elemento central en la mitad seleccionada se determina nuevamente y se compara con la clave.
- El proceso continúa hasta que se encuentra el elemento con el valor clave o el intervalo de búsqueda está vacío.
Aunque el código es bastante simple, hay algunas trampas.
- El código (first + last) / 2es erróneo si firste lastindividualmente encajan en su tipo, pero first+last no [1] . Si las matrices de un tamaño tan grande son teóricamente posibles, uno tiene que recurrir a trucos:
- Use un código first + (last - first) / 2que definitivamente no conducirá a desbordamientos cuando se trate de números enteros no negativos y first<last.
- Si firsty last son punteros o iteradores , dicho código es el único correcto, ya que no viola la abstracción (la operación «puntero + puntero» ya es incorrecta). Por supuesto, para preservar la complejidad del algoritmo, necesitamos operaciones rápidas “puntero+número → puntero”, “puntero−puntero → número”.
- Si firsty last son tipos con signo, realice el cálculo en el tipo sin signo: ((unsigned)first + (unsigned)last) / 2. En Java, el siguiente código funcionará: (first + last) >>> 1(la adición binaria con signo es lo mismo que sin signo, Java garantiza este comportamiento incluso en caso de desbordamiento, y toda esta fórmula opera en números con signo como sin signo).
- Escriba un cálculo en ensamblador usando la bandera de acarreo . Algo add eax, b; rcr eax, 1como Pero no es recomendable usar tipos largosfirst + (last - first) / 2 , es más rápido.
- Los errores de uno son comunes en las búsquedas binarias , y cada error de este tipo se convierte en un bucle , un salto o una matriz fuera de los límites. Por lo tanto, es importante probar estos casos: una matriz vacía ( n=0), un elemento ( n=1), buscando un valor faltante (demasiado grande, demasiado pequeño y en algún punto intermedio), buscando el primer y el último elemento.
- En ocasiones se requiere que, si xhay varias instancias en la cadena, no se encuentre ninguna, sino necesariamente la primera (como opción: la última; o ninguna x, sino el elemento que le sigue). [2] Por ejemplo, una función de C++ encuentra el primero de iguales y encuentra el elemento que sigue a x. Si no se encuentra, ambos regresan al lugar donde se insertó.std::lower_boundstd::upper_bound
El científico Jon Bentley afirma que el 90% de los estudiantes, al desarrollar una búsqueda binaria, se olvidan de tener en cuenta alguno de estos requisitos. E incluso en el código escrito por el propio Jon y yendo de un libro a otro, se deslizó un error: el código no es resistente a los desbordamientos [1] .
Ejemplo de implementación de Java
int búsqueda binaria ( int [] arr , int clave ) {
int bajo = 0 ;
int alto = arr . longitud - 1 ;
mientras ( bajo <= alto ) {
int mid = ( bajo + alto ) >>> 1 ;
int midVal = arr [ mid ] ;
si ( midVal < clave )
bajo = medio + 1 ;
si no ( midVal > clave )
alto = medio - 1 ;
más
volver medio ; // Llave encontrada
}
retorno - ( bajo + 1 ); // clave no encontrada.
}
Aplicaciones
Las aplicaciones prácticas del método de búsqueda binaria son variadas:
- Muy extendido en informática en relación a la búsqueda en estructuras de datos. Por ejemplo, la búsqueda en matrices de datos se realiza mediante la clave asignada a cada uno de los elementos de la matriz (en el caso más simple, el propio elemento es la clave).
- También se utiliza como método numérico para encontrar una solución aproximada a las ecuaciones (consulte el método de bisección ).
- El método se utiliza para encontrar el extremo de la función objetivo y en este caso es un método de optimización unidimensional condicional . Cuando una función tiene un argumento real, es posible encontrar una solución dentro del tiempo . Cuando el argumento es discreto e inicialmente se encuentra en un segmento de longitud N , la búsqueda de una solución llevará tiempo. Finalmente, para buscar un extremo, digamos, la certeza del mínimo , en el paso siguiente se descarta uno de los extremos del segmento considerado, cuyo valor es máximo.
Véase también
Notas
- ↑ 1 2 Extra, Extra - Lea todo sobre esto: Casi todas las búsquedas binarias y Mergesorts están rotas Archivado el 2 de diciembre de 2013 en Wayback Machine // Joshua Bloch, Google Research; traducción: casi todas las implementaciones de búsqueda binaria y clasificación por combinación tienen un error . Archivado el 24 de noviembre de 2013 en Wayback Machine .
- ↑ En C++ std::lower_bound , encuentra la primera aparición de xy encuentra el std::upper_bound elemento siguiente x.
Literatura
- Levitin A. V. Capítulo 4. Método de descomposición: búsqueda binaria // Algoritmos. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 180-183. — 576 pág. — ISBN 978-5-8459-0987-9
- Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Métodos computacionales para ingenieros. — M .: Mir, 1998.
- Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Métodos numéricos. - 8ª edición. - M. : Laboratorio de Conocimientos Básicos, 2000.
- Wirth N. Algoritmos + Estructuras de datos = Programas . - M. : " Mir ", 1985. - S. 28 .
- Volkov E. A. Métodos numéricos. — M. : Fizmatlit, 2003.
- Gill F., Murray W., Wright M. Optimización práctica. Por. De inglés. — M .: Mir, 1985.
- Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmos: construcción y análisis = Introducción a los Algoritmos / Ed. I. V. Krasikova. - 2ª ed. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
- Korn G., Korn T. Manual de matemáticas para científicos e ingenieros. - M. : Nauka, 1970. - S. 575-576.
- Korshunov Yu. M., Korshunov Yu. M. Fundamentos matemáticos de la cibernética. - Energía atomizada, 1972.
- Maksimov Yu. A., Filippovskaya EA Algoritmos para resolver problemas de programación no lineal. — M. : MEPHI, 1982.
- Roberto Sedgwick. Algoritmos fundamentales en C. Fundamentos/Estructuras de datos/Ordenación/Búsqueda. - San Petersburgo. : DiaSoftYUP, 2003. - S. 672. - ISBN 5-93772-081-4 .
Enlaces