二分法算法(水平等分图形面积)

二分法原理其实很像猜数字游戏:你知道答案在0到100之间,每次猜中间数,根据“大了”还是“小了”不断缩小范围,直到逼近正确答案。

二分法流程:

三、手算二分法全过程(迭代8次)

初始区间:最低点 low=0,最高点 high=4。
目标值:Starget=2.6667

迭代次数low (下限)high (上限)mid = (low+high)/2手算 A(mid) 公式代入A(mid) 数值比目标大/小?调整区间
10428−(4−2)2/2=8−26.00006 > 2.67(太大了)把上限降到 2
20218−(4−1)2/2=8−4.53.50003.5 > 2.67(还大)把上限降到 1
3010.58−(3.5)2/2=8−6.1251.87501.875 < 2.67(太小)把下限升到 0.5
40.510.758−(3.25)2/2=8−5.281252.71882.7188 > 2.67(略大)把上限降到 0.75
50.50.750.6258−(3.375)2/2=8−5.69532.30472.3047 < 2.67(略小)把下限升到 0.625
60.6250.750.68758−(3.3125)2/2=8−5.48632.51372.5137 < 2.67(还小)把下限升到 0.6875
70.68750.750.718758−(3.28125)2/2=8−5.38332.61672.6167 < 2.67(接近了)把下限升到 0.71875
80.718750.750.7343758−(3.265625)2/2=8−5.33222.66782.6678 ≈ 2.6667(命中!)停止

最终结果:经过8次迭代,我们得到水平线高度 h≈0.734375。

怎么把 h 变成实际的“起点和终点”?

检验结果:

注意需要做二分法的函数,必须要是单调递增,否则不能使用二分法!!!