基础算法 - 二分与三分 - 蒟蒻复习基础

　　二分是一种常用而且非常精妙的算法，常常是我们解决问题的突破口。二分的基本用途是在单调序列或单调函数中做查找操作。因此，当问题的答案具有单调性时，就可以通过二分把求解转化为判定（根据复杂度理论，判定的难度小于求解）。进一步的，我们还可以通过三分（适用于求解凸性函数）解决单峰函数的极值以及相关问题。

• 二分

　　思想：分而治之。将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，(如果子问题的规模仍然不够小,，再划分为k个子问题)，然后递归的求解这些子问题，最后用适当的方法将各个子问题的解合并成原问题的解。

　　方法：a）二分查找：在一个单调有序的集合或函数中查找一个解，每次分为左右两部分，判断解在哪个区间（并调节上下界），并直到找到目标元素。

int binary_search(int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (a[mid] == x) {
            return mid;
        }
        if (a[mid] < x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    return - 1;
}

　　　　   b）二分答案：（最大值最小或最小值最大这类问题）这类双最值问题常常选用二分法求解（二分之后，先假装自己确定答案），配合贪心，DP等算法，检验这个答案是否合理，将最优化问题转化为判定性问题。

　　　　   c）代替三分：（对于单峰函数）二分导函数求函数极值。

　　例题：Bzoj1734   Poj2018 ... ... 

　　题目描述

　　输入

　　输出

• 三分

　　适用于凸性函数的极值问题（二次函数就是一个典型的单峰函数）。与二分法强调函数的单调性不同，三分法强调函数的单峰性。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有