二进制搜索单调函数


二分查找不仅可以用于查找数组中的元素,还可以用于查找方程的根和单调(递增或递减)函数的值。

给我们一个单调函数 f 和这个函数的一些值 C。找到此函数的 x 参数的值,例如 \(f(x)=C\)
 
递增单调函数的例子:


我们选择函数值恰好大于和恰好小于给定值的边界。让我们选择该段中间的值。如果它小于给定的,那么我们将左边界移动到线段的中间。否则,我们将移动右边界。接下来,我们重复缩小边界的过程。但是有个问题就是什么时候停止搜索。阅读更多 此处
 
例如,考虑求数字x 的平方根的问题。 x 的平方根(由 \(\sqrt x\) 表示)是一个数字 y 使得\(y^2 = x\).
让我们将问题表述如下:对于给定的实数 x (\(x >= 1\)) 找到平方根,精度不少于点后 5 个字符。
 


选择段的边界进行搜索

由于我们无法检查整个无穷大的数字,因此我们需要定义搜索根的边界。首先,让我们找到左边界,选择任意负点(例如:-1)。我们将它加倍,直到它里面的值大于给定的值。为了找到正确的边界,我们选择任意一个正点(例如:1)。我们将它加倍,直到此时函数的值小于指定值。


或者,如果我们确切地知道搜索的边界,我们可以将 1 作为左边界,并将数字本身设为 x
之后,我们将当前段一分为二,中间平方,如果大于x,则替换上面,否则 底部。
 
最终实施:

在哪里,
eps - 必须寻求解决方案的准确性,
x - 给定的数字,我们正在寻找其平方根,
m - 算法执行后存储结果的数字。