[求助]折半查找是最优化的方案吗？

fffttt

[这个贴子最后由fffttt在 2011/11/01 09:13pm 第 1 次编辑]

这是一道数学化的问题，有一条很长的电缆，中间有一处断了，但外观看不出来，现在需要查找到故障点，可以任意截断电缆进行查找。
某人的办法是，从1/2处截断，查找那边有故障，然后在故障这边的1/2处截断，再缩小故障范围，然后又是剩下的1/2处截断……，最后截断X次后查找到了故障点。这个方法也是非常经典的方法了，我想了很久，有点疑惑“为什么非常从1/2处截断呢？假如从1/3处截断，然后再比较剩下的1/3段和2/3段，继续沿故障段的1/3处截断……”这样可以吗？

我倒觉得，从哪里截断都是一样的，比如黄金分割点处，或者第1次在1/2处截断，第2次在3/5处截断……
也就是说效率都是一样的呢？数学上有证明“折半”是最优化的方法吗？

ysr

是迭代法,折半是优化的,但不1定是最优化

天山草

这个问题早有定论，就是 0.618 这地方分断最优。