Búsqueda binaria

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

1. Determinar el valor de un elemento en medio de una estructura de datos. El valor resultante se compara con la clave.
2. 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.
3. 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.
4. 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