La búsqueda binaria se puede utilizar no solo para encontrar elementos en una matriz, sino también para encontrar las raíces de ecuaciones y los valores de funciones monótonas (crecientes o decrecientes).
Nos dan una función monotónica
f y algún valor
C de esta función. Encuentre el valor del argumento
x de esta función, tal que
\(f(x)=C\).
Ejemplo de una función monótona creciente:
Elegimos esos límites donde el valor de la función es exactamente mayor y exactamente menor que el valor dado. Elijamos el valor en el medio de este segmento. Si es menor que el dado, desplazamos el borde izquierdo al centro del segmento. De lo contrario, desplazaremos el borde derecho. A continuación, repetimos el proceso de estrechar los límites. Pero hay un problema que es cuando dejar de buscar. Leer más
aquí.
Por ejemplo, considere el problema de encontrar la raíz cuadrada del número x. La raíz cuadrada de x (denotado por \(\sqrt x\)) es un número y tal que < abarcan clase="matemáticas-tex">\(y^2 = x\).
Formulemos el problema de la siguiente manera: para un número real dado
x (
\(x >= 1\)) encuentre el raíz cuadrada con una precisión de no menos de 5 caracteres después del punto.
Seleccionar el borde del segmento para buscar
Ya que no podemos verificar la infinidad de números, necesitamos definir los límites de la búsqueda de la raíz. Primero, busquemos el borde izquierdo, seleccione un punto negativo arbitrario (por ejemplo: -1). Lo duplicaremos hasta que el valor en él sea mayor que el valor dado. Para encontrar el borde derecho, elegimos un punto positivo arbitrario (por ejemplo: 1). Lo duplicaremos hasta que el valor de la función en este punto sea menor que el especificado.
O, si conocemos exactamente los límites de la búsqueda, podemos tomar 1 como el límite izquierdo y el número en sí mismo
x.
Después de eso, dividimos el segmento actual por la mitad, elevamos al cuadrado el medio y, si es mayor que x, reemplazamos la cara superior; de lo contrario, abajo.
Implementación final: