软件设计师11-数据结构及算法应用

分治法

对一个规模为n的问题，若该问题可以容易地解决（比如n较小）则直接解决；否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解

该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解为若干个规模较小的相同问题
利用该问题分解出的子问题的解可以合并为该问题的解
该问题所分解出的各个子问题是相互独立的

分解、解决、合并

递归

在运行的过程中调用自己

c++
// 斐波那契数列递归求解
int F(int n)
{
    if(n == 0) return 1;
    if(n == 1) return 1;
    if(n > 1) return F(n - 1) + F(n - 2);
}

应用：二分查找

javascript
/**
 * L: 要查找的数列
 * a, b: 要查找的区间范围起点和终点
 * x: 要查找的值
 */
function Binary_Search(L, a, b, x) {
    if (a > b) {
        return (-1)
    } else {
        const m = (a + b) / 2;
        if (x === L[m]) {
            return m
        } else if (x > L[m]) {
            return Binary_Search(L, m + 1, b, x)
        } else {
            return Binary_Search(L, a, m - 1, x)
        }
    }
}