二分算法学习总结，心得体会

罗勇军老师的第一遍博客写的是关于二分法和三分法，主要内容是二分法 链接: 算法竞赛专题解析（1）：二分法、三分法.

1.二分法适用的题目类型

二分非常高效。所以，如果问题是单调性的，且求解精确解的难度很高，可以考虑用二分法。（这是原话） 总结一下有两点：1.问题是单调的，有时候需要手动排序。2.求解的精度很高，在实数二分的时候，就要控制二分的精度了。

2.整数二分问题

2.1解题模板

while (left < right) { int ans; //记录答案 int mid = left+(right-left)/2; //二分 if (check(mid)){ //检查条件，如果成立 ans = mid; //记录答案 … //移动left（或right） } else … //移动right（或left） }

check函数非常重要，它的作用是检查mid是否符合条件。那么问题就来了，如何检查。这个地方出题者可以大做文章，可以跟很多其他的知识进行结合考察。

2.2主要问题类型

最小化最大值问题最大化最小值问题 下面这段代码是我昨天晚上尝试这写“通往奥格瑞玛的道路”这个题的一个半成品的代码。放一个没写出来的代码在这里，主要是感觉这个题综合性太大，很多知识还没学好，写出来很困难。

这是一份尚未完成的代码，昨天自闭了一晚上，尽管已经看懂了算法的步骤，还是感觉很多知识没学好，写不出来。

#include<bits/stdc++.h> using namespace std; // 邻接矩阵 typedef struct _graph { int vexs[MAX]; // 顶点集合 int vexnum; // 顶点数 int edgnum; // 边数 int matrix[MAX][MAX]; // 邻接矩阵 }Graph, *PGraph; // 边的结构体 typedef struct _EdgeData { char start; // 边的起点 char end; // 边的终点 int weight; // 边的权重 }EData; int dijkstra(Graph G, int vs, int prev[], int dist[]){ int i,j,k; int min; int tmp; int flag[MAX]; // flag[i]=1表示"顶点vs"到"顶点i"的最短路径已成功获取。 // 初始化 for (i = 0; i < G.vexnum; i++) { flag[i] = 0; // 顶点i的最短路径还没获取到。 prev[i] = 0; // 顶点i的前驱顶点为0。 dist[i] = G.matrix[vs][i];// 顶点i的最短路径为"顶点vs"到"顶点i"的权。 } // 对"顶点vs"自身进行初始化 flag[vs] = 1; dist[vs] = 0; // 遍历G.vexnum-1次；每次找出一个顶点的最短路径。 for (i = 1; i < G.vexnum; i++) { // 寻找当前最小的路径； // 即，在未获取最短路径的顶点中，找到离vs最近的顶点(k)。 min = INF; for (j = 0; j < G.vexnum; j++) { if (flag[j]==0 && dist[j]<min) { min = dist[j]; k = j; } } // 标记"顶点k"为已经获取到最短路径 flag[k] = 1; // 修正当前最短路径和前驱顶点 // 即，当已经"顶点k的最短路径"之后，更新"未获取最短路径的顶点的最短路径和前驱顶点"。 for (j = 0; j < G.vexnum; j++) { tmp = (G.matrix[k][j]==INF ? INF : (min + G.matrix[k][j])); // 防止溢出 if (flag[j] == 0 && (tmp < dist[j]) ) { dist[j] = tmp; prev[j] = k; } } } printf("dijkstra(%c): \n", G.vexs[vs]); for (i = 0; i < G.vexnum; i++) printf(" shortest(%c, %c)=%d\n", G.vexs[vs], G.vexs[i], dist[i]); } int main(){ int n,m,b; cin>>n>>m>>b; int fi[n];//经过城市i，需要交费fi元 for(int i=0;i<n;i++){ cin>>fi[i]; } int ai[m]; int bi[m]; int ci[m];//ai城到bi城需要ci的血量 for(int i=0;i<m;i++){ cin>>ai[i]>>bi[i]>>ci[i]; } //二分 sort(fi,fi+n-1) ;//对fi进行排序 int left=0;int right=n; while(left<right){ int mid=left+(right-left)/2; // //将当前条件转化为一张图 Graph G;//图 G.vexnum=n; //写不出来了，脑阔疼。。。 /// if(b>=dijkstra(,)){//求最短路径问题 dijkstra算法，删除所有大于fi的点，在剩下的点中，求1到N的最短路。 right=mid;//满足条件去找更小的fi } else{ left=mid;//不满足条件则fi需要增大 } } return fi[left]; }

3.实数二分问题

3.1解题模板

const double eps =1e-7; //精度。如果下面用for，可以不要eps while(right - left > eps){ //for(int i = 0; i<100; i++){ double mid = left+(right-left)/2; if (check(mid)) right = mid; //判定，然后继续二分 else left = mid; }

两种不同的循环方法都是为了控制了精度。

3.2主要问题类型

其实跟整数二分差不多，只是在check函数上要根据题目做相应的变化。一定要读懂题目。

4.三分法求极值

三分法用来求一个单峰（或者单谷）的极值，是二分法的一个简单扩展。具体内容我就不再这赘述了。跟二分法非常类似。

5.其他知识积累

c++的STL中有lower_bound()和upper_bound()两个函数，他们的主要作用是，在不改变数组有序性的前提下，插入一个值，找到这个值的插入位置。区别：lower_bound()是从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。upper_bound()是从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。一个等于的区别。但是两个函数联合起来就真的是1+1>2了。 1.查找第一个大于x的元素的位置：upper_bound()。代码例如： 　　　　　　　　pos = upper_bound(a, a+n, test) - a; 2.查找第一个等于或者大于x的元素：lower_bound()。 3.查找第一个与x相等的元素：lower_bound()且 = x。 4.查找最后一个与x相等的元素：upper_bound()的前一个且 = x。 5.查找最后一个等于或者小于x的元素：upper_bound()的前一个。 6.查找最后一个小于x的元素：lower_bound()的前一个。 7.单调序列中数x的个数：upper_bound() - lower_bound()。 在计算mid时的一个小细节我感觉需要注意一下：最好是用left+（right-left）/2而不是直接（left+right）/2。我之前经常用后一种，也没感觉有什么问题。但是当right和left都很大时，就很有可能发生越界导致程序出错。

6.明日更新内容

明天将会更新二分法和三分法的习题，可能会需要两天时间。但是我会尽快更新的！！！能一天绝不两天。