二分法的原理及其应用举例

首先，什么���二分法：

        最简单的例子就是类似于二分查找的用法来实现快速查找有序区间内的给定的目标值是否存在，当然，这也可以应用在别的问题中，二分查找是一个时间效率极高的算法，尤其是面对大量的数据时，其查找效率是极高，时间复杂度是log(n)。如果问题是单调的，且求解精确解的难度很高，可以考虑用二分法。
主要思想就是不断的对半折叠，每次查找都能除去一半的数据量，直到最后将所有不符合条件的结果都去除，只剩下一个符合条件的结果。

二分法看似简单，实则在细节上非常容易出错，要注意终止边界，左右区间开闭情况，避免漏掉答案和陷入***循环，在了解了最简单的基本原理之后，我们来由简入繁地以题目来入手理解这个算法，

1.关键的mid的处理

在整个二分法中，对于mid的处理至关重要，如果取值不当，while很容易会***循环，我们来分三点讨论这个问题：

1.1left=mid+1能否写成left=mid？

     在实数二分中，确实是left=mid，right=mid，但是在整数二分中存在取整问题，如果取left=mid，会造成原来的left和right值不改变，所以while循环会一直进行下去造成***循环，取left=mid+1则不会。

1.2 不同问题下的mid取值问题

    我们要根据不同的问题来识别到底需要左中位数还是右中位数，即对于mid的取值，我们可以向上取整同样的也可以向下取整，要看具体问题的逻辑，我们一般的都使用左中位数，即靠近left的那个数；

1.3谨慎使用（left+right）/2

我们都知道，除法的取整会导致在正负区间左右的中位数计算不一致，虽然一般的情况下，left和right都是正数，在实际计算中，我们可以用mid=left+（right-left）/2或者是mid=（left+right）>>1来替换即可，综合来看，还是（left+right）>>1更优。

下面我们还是来通过例题理解这些知识：

例题一

经典的最大值最小化模型

 

 首先，我们怎样把二分法应用到这个题的求解中，我们知道这个题其实就是想让我们在划分的数组中求出无论怎样划分，其每个分子数组产生的和都有一个确定的最小值，而这个最小值一定介于原数组中的最大的一个元素（最小划分为一个数组）和原数组的所有数组元素的和（最大的一个分组）之间，我们可以在这两个边界之间枚举我们的最大值，采用二分法来寻找最小的那一个数。

我们在代码中来解释细节问题

#include #include int n, m;int l, r, mid, ans;int a[100010];//二分答案，枚举出一个最大值，根据分组情况调整最大值，求出最优最大值。/* * check 函数 * 作用: *根据枚举出的最大值，来分组，根据分出的组数来调整最大值 * 变量: *x : 枚举出的最大值 *sum : 分组时每组的和 *count : 分出的组数 */bool check(int x){    int sum=0, count=0;//t2: 组数 t1: 每组的和    for(int i=0; i