二分算法 cpp

7. 二分算法基础算法中最难的原理与模板简单难点在细节处理边界问题解集中存在二段性模板题 :[!leetcode]34. 在排序数组中查找元素的第一个和最后一个位置中等给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。示例 1**输入**nums [5,7,7,8,8,10], target 8输出[3,4]示例 2**输入**nums [5,7,7,8,8,10], target 6输出[-1,-1]示例 3**输入**nums [], target 0输出[-1,-1]提示0 nums.length 105-109 nums[i] 109nums是一个非递减数组-109 target 109思路:题目要求 - 找到 起始位置 和 初始位置方一 - 暴力解法 - 从前往后扫描数组 - O(n)暴力解法慢在没有利用数组的有序性方二 - 二分算法查找起始位置left---------------mid---------------righta[mid] t ; right mid ; [left, right];a[mid] t ; left mid 1 ; [left, right]细节问题:while循环的判断条件while ( left right ); √while ( left right );不能, 可能会死循环 , eg:[2,2]求中点的方法方一 :( left right ) / 2- 奇数中点靠左 √方二 :( left right 1 ) / 2- 奇数中点靠右 - 死循环 -[2, 2]二分结束后, 相遇点的情况(容易忽略)判断循环结束后的结果是否为我们所需查找终止位置left---------------mid---------------righta[mid] t; left mid ; [left, right]a[mid] t ; right mid - 1; [left, right]细节问题:while循环的判断条件while ( left right ); √while ( left right );不能, 可能会死循环 , eg:[2,2]求中点的方法方一 :( left right ) / 2- 奇数中点靠左 - 死循环 -[2, 2]方二 :( left right 1 ) / 2- 奇数中点靠右 √二分结束后, 相遇点的情况(容易忽略)判断循环结束后的结果是否为我们所需代码:(二分模板)//二分查找区间的左端点intl1,rn;while(lr){intmid(lr)/2;if(check(mid))rmid;elselmid1;}//二分结束后可能需要判断是否存在结果//二分查找区间的右端点intl1,rn;while(lr){intmid(lr1)/2;if(check(mid))lmid;elsermid-1;}//二分结束之后可能需要判断是否存在结果有时会溢出( lr int的范围 ), 可采用mid l ( r - l ) / 2 ;mid l ( r - l 1 ) / 2 ;或者用long long定义模板不要死记 , 具体题目具体分析时间复杂度 — 二分的次数 —O ( l o g N ) O(log N)O(logN)STL 中的二分查找algorithmlower_bound: 大于等于 x 的最小元素, 返回迭代器 ,O ( l o g N ) O(log N)O(logN)uooer_bound: 大于 x 的虽小元素, 返回迭代器,O ( l o g N ) O(log N)O(logN)使用方法:auto it lower_bound(左端点 闭区间,右端点 开区间, 数字);auto it lower_bound(a1 , a n 1 , target) ;int a *it- 解引用均采用二分查找实现, 但STL中的这个仅仅只适用于在有序的数组中查找 , 二分答案不能用7.2 二分答案7.2.1 木材加工(二分答案模板题目)[!洛谷]P2440 木材加工题目背景要保护环境。题目描述木材厂有n nn根原木现在想把这些木头切割成k kk段长度均为l ll的小段木头木头有可能有剩余。当然我们希望得到的小段木头越长越好请求出l ll的最大值。木头长度的单位是cm \text{cm}cm原木的长度都是正整数我们要求切割得到的小段木头的长度也是正整数。例如有两根原木长度分别为11 1111和21 2121要求切割成等长的6 66段很明显能切割出来的小段木头长度最长为5 55。输入格式第一行是两个正整数n , k n,kn,k分别表示原木的数量需要得到的小段的数量。接下来n nn行每行一个正整数L i L_iLi​表示一根原木的长度。输出格式仅一行即l ll的最大值。如果连1cm \text{1cm}1cm长的小段都切不出来输出0。输入输出样例 #1输入 #13 7 232 124 456输出 #1114说明/提示数据规模与约定对于100 % 100\%100%的数据有1 ≤ n ≤ 10 5 1\le n\le 10^51≤n≤1051 ≤ k ≤ 10 8 1\le k\le 10^81≤k≤1081 ≤ L i ≤ 10 8 ( i ∈ [ 1 , n ] ) 1\le L_i\le 10^8(i\in[1,n])1≤Li​≤108(i∈[1,n])。思路:方一 : 暴力解法枚举所有的切割长度 x求 x 情况下 , 能切出来几段方二 : 利用二分优化方一x - 切割出小段的长度 c - 在 x 的基础下 , 最多能切出的段数 k - 最终要切出的段数设 ret 为最终结果(段数) c k;±-------------±--------------left 0 mid right maxlen代码:#includebits/stdc.husingnamespacestd;constintN1e510;typedeflonglongLL;LL n,k;LL l[N];LLcalc(LL x){LL cnt0;for(inti1;in;i){cntl[i]/x;}returncnt;}intmain(){cinnk;for(inti1;in;i)cinl[i];intleft0,right1e8;while(leftright){LL mid(leftright1)/2;if(calc(mid)k)leftmid;elserightmid-1;}coutleft;return0;}