1.二分法的本质

二分法：函数单调性+计算内容重复
不同于分治法
二分法：猜答案位置mid->判定并修正（求答案->求判定）

闭区间：[s, e] -> [s, mid - 1] mid [mid + 1, e]，运行条件s <= e
开区间：[s, e) -> [s, mid) mid [mid + 1, e)，运行条件s < e
对于连续域：[s, mid) + [mid, e) = [s, e)

69. Sqrt(x)
可用牛顿迭代法和二分法

1）一般情况下假设可取区间是左闭右开，[L, R)，这样二分法的情形如下：
while(L < R) {
    long mid = (L + R) / 2;
    if (guess(mid, x)) {
        L = mid + 1;
    } else {
        R = mid;
    }
}

2）乘法，加法都需要考虑溢出问题，所以定义类型的时候都需要定义为long或long long类型
3）可以将满足情况的值放在ans里面，最后返回ans
4）对于离散型的数字，不要将mid一直放到新区间里面，使用L = mid + 1等去掉！

410. Split Array Largest Sum

1）一个很重要的单调性：
ans = f(m)为单调减函数，所以框架要更换！
ans是返回的值，m是划分的块数！
2）注意加法溢出情况
3）左闭右开需要将右边的+1：
        long R = 1; //左闭右开
        for (int i = 0; i < n; ++i) {
            R += nums[i];
        }
        int L = 0; 
        long ans = 0;
        while (L < R) {
            long mid = (L + R) /2;
            if (guess(mid, nums, m)) {
                ans = mid;
                R = mid;
            } else {
                L = mid + 1;
            }
        }
        return (int)ans;
4）这题解法的根本在guess函数，使用贪心算法以及特别注意一个判断问题
    bool guess (long mid, vector<int>& nums, int m) { // Greedy
        long sum = 0;
        for ( int i = 0; i < nums.size(); ++i) {
            if ( sum + nums[i] > mid) {
                --m;
                sum = nums[i];
                if (nums[i] > mid) {
                    return false; // Attention
                }
            } else {
                sum += nums[i];
            }
        }
        
        return m >= 1;
    }

363. Max Sum of Rectangle No Larger Than K

容斥原理：
1）二维：求出sum(i, j)（表示从(0, 0)到(i, j)的矩形面积），可以求出任意的矩形的面积。
2）一维：sum(j) - sum(i) <= k，把二维变为一维
也即：sum(j) <= k + sum(i)，k与sum(i)负相关

378. Kth Smallest Element in a Sorted Matrix

k越大，数值越大。
给定数值，比较容易定位k的值！
1）这里利用了闭区间的单调增二分法：
        int R = matrix[n-1][n-1]; //[L, R]
        int L = matrix[0][0];
        int ans = 0;
        while (L <= R) {
            long mid = (int)(((long)L + R) / 2);
            if (guess(mid, matrix, k, n)) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }
2）数字重复时，guess函数容易出问题，辨析如下两个guess的细微区别：
    bool guess(int gue, vector<vector<int>>& matrix, int k, int n) {
        int sum2 = 0;
        for (int i = 0; i < n; ++i) {
            int L = 0; int R = n -1;
            int ans = -1;
            while(L <= R) {
                int mid = (int)(((long)L + R) /2);
                if (matrix[i][mid] <= gue) {
                    ans = mid; 
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            sum2 += (ans + 1);
        }
        return k >= sum2;
    }
可以通过画图来分析上面一个是错误的，下面时正确的
    bool guess(int gue, vector<vector<int>>& matrix, int k, int n) {
        int sum2 = 0;
        for (int i = 0; i < n; ++i) {
            int L = 0; int R = n -1;
            int ans = -1;
            while(L <= R) {
                int mid = (int)(((long)L + R) /2);
                if (matrix[i][mid] < gue) {
                    ans = mid; 
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            sum2 += (ans + 1);
        }
        return k > sum2;
    }

2.倍增法（利用重复）

50. Pow(x, n)

凡是有如下情况就需要防止溢出：
1）加法
2）取反 n -> -n，因为不对称，这个本质也是乘法
3）乘法
    double myPow(double x, int n) {
        if(n == 0)
            return 1;
        long m = 0;
        if(n<0){
            m = (long)n * (-1);
            x = 1/x;
        } else {
            m = n;
        }
        return (m%2 == 0) ? pow(x*x, m/2) : x*pow(x*x, m/2);        
    }

斐波那契->快速幂

快速幂转换