分治 —— 二分法

本文主要是介绍分治 —— 二分法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【概述】

二分法，是十分常见的问题，其在一个单调有序的集合或函数中查找一个解，每次分为左右两部分，通过判断解在哪部分来调整上下界，直到找到目标元素，其与各种算法的结合比较密切，关于其原理：点击这里

若求解的问题的定义域为整数域，对于长度为 n 的求解区间，算法需要 logn 次来确定分界点；若求解的问题的定义域是实数域，由于实数运算的精度问题，则判定 R-L 的精度是否达到要求是问题的关键，即：R-L>=EPS，若 EPS 取的过小会导致程序死循环。

【实现】

除了查找元素、查找连续函数外，还可以使用 STL 容器中的 lower_bound()、upper_bound() 函数，具体使用：点击这里

1.查找元素

int BinarySearch(int a[],int x,int x){int left=0;//left为集合下界int right=n-1//right为集合上界int res=-1;while(left<=right){int mid=(left+right)/2;//设置中值if(num[mid]==x){//查找到符合元素xres=mid;break;}else if(num[mid]<x)//x在右边部分low=mid+1;//调整集合下界else//x在左边部分high=mid-1;//调整集合上界}return res;//若未找到x，则res= -1
}

2.查找连续函数

#define EPS 1E-9
bool cal(int x){...
}
int BinarySearch(double low,double high){//low为区间下界，high为区间上界double mid;//中值double left=low;//设置当前查找区间上界的初值double right=high;//设置当前查找区间下界的初值while(right-left>EPS){mid=(right+left)/2;//设置中值if(cal(mid)<x)//函数结果小于带查找的值left=mid;//说明在右边部分，调整集合下界elseright=mid;//说明在左边部分，调整集合上界}return mid;
}

【例题】

1.查找元素

1. 丢瓶盖（洛谷-P1316）：点击这里
2. Block Towers（CF-626C）：点击这里
3. Widespread（AtCoder-2580）：点击这里
4. Aggressive cows（POJ-2456）：点击这里
   同题：愤怒的牛（信息学奥赛一本通-T1433）：点击这里
5. River Hopscotch（POJ-3258）：点击这里
   同题：河中跳房子（信息学奥赛一本通-T1247）：点击这里
6. Can you find it?（HDU-2141）：点击这里
7. Median（POJ-3579）：点击这里
8. 相离的圆（51Nod-1278）(lower_bound() 函数)：点击这里
9. Points on Line（CF-252C）(upper_bound() 函数)：点击这里
10. Monthly Expense（ POJ-3273）(最小组数和)：点击这里
    同题：月度开销（信息学奥赛一本通-T1243）：点击这里
11. 数列分段`Section II`（洛谷-P1182）(二分+累加和)：点击这里
    数列分段II（信息学奥赛一本通-T1436）：点击这里
12. Go Home（AtCoder-2354）(二分+前缀和)：点击这里
13. Artificial Lake（POJ-3658）(二分+模拟)：点击这里
14. The hat（CF-1020D）(二分+格式控制输出)：点击这里
15. 查找最接近的元素（信息学奥赛一本通-T1240）(二分+绝对值比较)：点击这里
16. Gadgets for dollars and pounds（CF-609D）(二分+贪心)：点击这里
17. 炫酷划线（2019牛客寒假算法基础集训营 Day5-E）(二分+栈)：点击这里
18. 只包含因子 2 3 5 的数（51Nod-1010）(二分+打表)：点击这里
19. Sweets for Everyone!（CF-248D）(二分+模拟)：点击这里
20. No Need（AtCoder-2346）(bitset+二分)：点击这里

2.查找连续函数

1. 二分法求函数的零点（信息学奥赛一本通-T1241）：点击这里
2. 一元三次方程求解（信息学奥赛一本通-T1238）：点击这里
3. Can you solve this equation?（HDU-2199）：点击这里
4. Pie（HDU-1969）：点击这里
5. Cable master（HDU-1551）：点击这里
   同题：网线主管（信息学奥赛一本通-T1242）：点击这里
6. 膨胀的木棍（信息学奥赛一本通-T1246）(二分+数学推导)：点击这里

这篇关于分治 —— 二分法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---