1. 什么是减治法

**减治法（reduce and conquer method）把一个大问题划分为若干个子问题，但是只需求解其中的一个子问题，也无需对子问题的解进行合并。**所以，严格地说，减治法应该是一种退化了的分治法。

2. 减治法的设计思想

原问题（规模为 n）的解与子问题（规模通常为 n/2）的解之间存在某种确定的关系，这种关系通常表现为：

（1） 原问题的解只存在于其中一个较小规模的子问题中;

（2） 原问题的解与其中一个较小规模的解之间存在某种确定的对应关系。

3. 减治法常见问题

3.1 折半查找

应用折半查找方法在一个升序序列中查找值为k的元素。若查找成功，返回元素 k 在序列中的位置，若查找失败，返回失败信息。

算法思路：折半查找利用序列有序的特点，其查找过程是：取序列的中间元素作为比较对象，若 k 与中间元素相等，则查找成功；若 k 小于中间元素，则在中间元素的左半区继续查找；若 *k 大于中间记录，则在中间元素的右半区*继续查找。不断重复上述过程，直到查找成功，或查找区间为空，查找失败。

例如，在有序序列{7,14,18,21,23,29,31,35,38}中查找18。

算法描述如下：

算法：折半查找BinSearch
输入：有序序列{r1, r2, …, rn}，待查值 k
输出：若查找成功，返回记录 k 的位置，若查找失败，返回失败标志 0
       1. 设置初始查找区间：low = 1；high = n；  
       2. 测试查找区间［low，high］是否存在，若不存在，则查找失败，返回 0；
       3. 取中间点 mid = (low+high)/2; 比较 k 与 rmid，有以下三种情况：
            3.1 若 k < rmid，则 high = mid - 1；查找在左半区进行，转步骤2；         
            3.2 若 k > rmid，则 low = mid + 1；查找在右半区进行，转步骤2；        
            3.3 若 k = rmid，则查找成功，返回记录在表中位置 mid；

时间复杂度：O(log2n)