二分法算法(水平等分图形面积)
二分法原理其实很像猜数字游戏:你知道答案在0到100之间,每次猜中间数,根据“大了”还是“小了”不断缩小范围,直到逼近正确答案。
二分法流程:
三、手算二分法全过程(迭代8次)
初始区间:最低点 low=0,最高点 high=4。
目标值:Starget=2.6667
| 迭代次数 | low (下限) | high (上限) | mid = (low+high)/2 | 手算 A(mid) 公式代入 | A(mid) 数值 | 比目标大/小? | 调整区间 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 8−(4−2)2/2=8−2 | 6.0000 | 6 > 2.67(太大了) | 把上限降到 2 |
| 2 | 0 | 2 | 1 | 8−(4−1)2/2=8−4.5 | 3.5000 | 3.5 > 2.67(还大) | 把上限降到 1 |
| 3 | 0 | 1 | 0.5 | 8−(3.5)2/2=8−6.125 | 1.8750 | 1.875 < 2.67(太小) | 把下限升到 0.5 |
| 4 | 0.5 | 1 | 0.75 | 8−(3.25)2/2=8−5.28125 | 2.7188 | 2.7188 > 2.67(略大) | 把上限降到 0.75 |
| 5 | 0.5 | 0.75 | 0.625 | 8−(3.375)2/2=8−5.6953 | 2.3047 | 2.3047 < 2.67(略小) | 把下限升到 0.625 |
| 6 | 0.625 | 0.75 | 0.6875 | 8−(3.3125)2/2=8−5.4863 | 2.5137 | 2.5137 < 2.67(还小) | 把下限升到 0.6875 |
| 7 | 0.6875 | 0.75 | 0.71875 | 8−(3.28125)2/2=8−5.3833 | 2.6167 | 2.6167 < 2.67(接近了) | 把下限升到 0.71875 |
| 8 | 0.71875 | 0.75 | 0.734375 | 8−(3.265625)2/2=8−5.3322 | 2.6678 | 2.6678 ≈ 2.6667(命中!) | 停止 |
最终结果:经过8次迭代,我们得到水平线高度 h≈0.734375。
怎么把 h 变成实际的“起点和终点”?
检验结果:
注意需要做二分法的函数,必须要是单调递增,否则不能使用二分法!!!
