分而治之是算法设计中的一种方法。它将一个问题分成多个和原问题相似的小问题,递归解决小问题,再将解决方式合并以解决原来的问题。分而治之算法可以分成三个部分:
(1) 分解原问题为多个子问题(原问题的多个小实例)。
(2) 解决子问题,用返回解决子问题的方式的递归算法。递归算法的基本情形可以用来解决子问题。
(3) 组合这些子问题的解决方式,得到原问题的解。
例子:使用分而治之的方式实现二分搜索,逻辑如下:
分解:计算mid并搜索数组较小或较大的一半。
解决:在较小或较大的一半中搜索值。
合并:这步不需要,因为我们直接返回了索引值。
1 | function binarySearchRecursive( |