三分查找
三分查找用于求单峰函数的极值。 速度快，但是结果并非准确值。 方法 首先，在函数上标 4个 点： x = l e , r t , m i d , m m i d x = l e , r t , m i d , m m i d 。其中 m m i d m m i d 是 m i d m i d 与 r t r t 的中点。 现在的任务是通过 迭代 缩小范围： 如果 f ( m i d ) > f ( m m i d ) f ( m i d ) > f ( m m i d ) ，则 m m i d m m i d 一定在峰的右边。 如果 f ( m i d ) < f ( m m i d ) f ( m i d ) < f ( m m i d ) ，则 m i d m i d 一定在峰的左边。 证明： 1. 我们假设存在 f ( m i d ) > f ( m m i d ) f ( m i d ) > f ( m m i d ) 且 m m i d m m i d 在峰的左边。 由于 f ( x ) f ( x ) 在峰的左边单调递增，且 f ( m i d ) > f ( m m i d ) f ( m i d ) > f ( m m i d ) ，所以 m i d m i d 在 m m i d m m i d 的 右边 。 然而 m m i d = m i d + r t 2 m m i d = m i d + r t 2 ，显然 m i d m i d 在 m m i d m m i d 左边 。矛盾。 2. 我们假设存在 f ( m i d ) < f ( m m i d ) f ( m i d ) < f ( m m i d ) 且 m i d m i d 在峰的右边。 由于 f ( x ) f ( x ) 在峰的右边单调递减，且 f ( m i d ) < f ( m m i d ) f ( m i d ) < f ( m m i d ) ，所以 m i d m i d 在 m m i d m m i d 的 右边 。 然而 m m i d = m i d + r t 2 m m i d = m i d + r t 2 ，显然 m...