二分思想在算法中的应用（二分查找/答案）

二分查找概念在一个有序数组中查找某元素通过判断区间中间的元素与目标元素的大小关系反复将区间缩小为原先一半从而把普通的遍历数组查询的时间复杂度O(n)优化为O(log n)。实现为了更符合直觉这里不使用数组的第一个元素也就是arr[0]并且默认升序排序intbinarySearch(constvectorintarr,intnum){intlengtharr.size()-1;intL1;intRlength;while(L1R){intmidL(R-L1)//使用位运算加快速度同时不用LR避免数字过大而溢出if(arr[mid]num)returnmid;if(arr[mid]num){Rmid;continue;}else{Lmid;continue;}}return-1;}二分答案概念本质枚举这种算法将二分查找推广到了更多的领域只要数据满足广义上的有序便可使用通过二分的思想让枚举的速度加快但首先需要能够判断答案的真假作为枚举的基础。理解广义有序例如数据可以被某表达判定真假规定左侧全是真右侧全是假便可以用二分查找到真与假的边界举一个形象的例子我们规定有一个数组装着1到20的数字并且10的左边全部比10小右边全部比10大那么哪怕这个数组并不严格在所有局部上都满足升序的排列我们依旧可以查找到10的位置。应用以一道例题举例P2678 [NOIP 2015 提高组] 跳石头一年一度的“跳石头”比赛又要开始了这项比赛将在一条笔直的河道中进行河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间有 N 块岩石不含起点和终点的岩石。在比赛过程中选手们将从起点出发每一步跳向相邻的岩石直至到达终点。为了提高比赛难度组委会计划移走一些岩石使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制组委会至多从起点和终点之间移走 M 块岩石不能移走起点和终点的岩石。输入格式第一行包含三个整数 L,N,M分别表示起点到终点的距离起点和终点之间的岩石数以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。先让我们做出一些尝试显然要让最小距离尽量小是很容易的即标准答案也就是最小距离的最大值之下的距离值是容易被满足而之上是不可能满足的则答案满足广义的有序那么如果我们有一个表达式可以判定我所枚举的值是否能够被满足则可以用二分答案大大减少我们枚举的次数。