二分分为实数二分二分理论题二分套路题最小值最大化最大值最小化运用二分满足条件有界单调。-1.四种二分模板//模板 1左闭右闭 [l, r] —— 最常用 int l 0, r n - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) { l mid 1; } else { r mid - 1; } } return l; /* 作用 找第一个 ≥ target 的位置 特点 无死循环 mid 不用 1 最终 l 第一个 ≥ target 最终 r 最后一个 target */ // 模板 2左闭右开 [l, r) —— 找第一个满足条件 int l 0, r n; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) { l mid 1; } else { r mid; } } return l; /* 作用 找第一个 ≥ target */ //模板 3左开右闭 (l, r] —— 找最后一个满足条件 int l -1, r n - 1; while (l r) { int mid l (r - l 1) / 2; // 必须 1防死循环 if (nums[mid] target) { l mid; } else { r mid - 1; } } return l; /* 作用 找最后一个 ≤ target 关键 出现 l mid ⇒ mid 必须 1 */ //模板 4开区间 (l, r) —— 很少用 int l 0, r n - 1; while (l 1 r) { int mid l (r - l) / 2; if (nums[mid] target) l mid; else r mid; } /* */模板区间循环条件mid 是否 1返回功能1[l, r] 闭区间l r不加l第一个 ≥ target2[l, r)l r不加l第一个 ≥ target3(l, r]l r必须 1l最后一个 ≤ target闭区间写法1. 找第一个 ≥ target的位置lower_boundif nums[mid] target: right mid - 1 else: left mid 1 return left✅符号2. 找第一个 target的位置if nums[mid] target: right mid - 1 else: left mid 1 return left✅符号3. 找最后一个 ≤ target的位置if nums[mid] target: left mid 1 else: right mid - 1 return right✅符号4. 找最后一个 target的位置if nums[mid] target: left mid 1 else: right mid - 1 return right✅符号0.三种二分模版# lower_bound 返回最小的满足 nums[i] target 的 i # 如果数组为空或者所有数都 target则返回 len(nums) # 要求 nums 是非递减的即 nums[i] nums[i 1] # 闭区间写法 def lower_bound(nums: List[int], target: int) - int: left, right 0, len(nums) - 1 # 闭区间 [left, right] while left right: # 区间不为空 # 循环不变量 # nums[left-1] target # nums[right1] target mid (left right) // 2 if nums[mid] target: left mid 1 # 范围缩小到 [mid1, right] else: right mid - 1 # 范围缩小到 [left, mid-1] return left # 左闭右开区间写法 def lower_bound2(nums: List[int], target: int) - int: left 0 right len(nums) # 左闭右开区间 [left, right) while left right: # 区间不为空 # 循环不变量 # nums[left-1] target # nums[right] target mid (left right) // 2 if nums[mid] target: left mid 1 # 范围缩小到 [mid1, right) else: right mid # 范围缩小到 [left, mid) return left # 或者 right # 开区间写法 def lower_bound3(nums: List[int], target: int) - int: left, right -1, len(nums) # 开区间 (left, right) while left 1 right: # 区间不为空 mid (left right) // 2 # 循环不变量 # nums[left] target # nums[right] target if nums[mid] target: left mid # 范围缩小到 (mid, right) else: right mid # 范围缩小到 (left, mid) return right1.两个二分模板找x的第一个midlowhigh//2 没有就找比他大的下一个数a[0,3,5,7,9,11,13] # [0,1,2,3,4,5,6] # low 0 high 6 mid 3 ----- low4 high 6 # low 4 high 6 mid 5 ----- low4 high 5 # low 4 high 5 mid 4 ----- low5 high 5 # break lowhigh5 # 找的是靠右的那一个 low0 highlen(a)-1 def search(low,high,x): # 查找的是后一个 while (lowhigh): mid (lowhigh)//2 # (23)//22 偏左 if (a[mid]x): highmid else: lowmid1 print(a[low]) print(a[high]) search(low,high,10) # 查找结果10找x的第一个midlowhigh1//2 没有就找比他小的前一个数a[0,3,5,7,9,11,13] # [0,1,2,3,4,5,6] # low 0 high 6 mid 3 ----- low3 high 6 # low 3 high 6 mid 5 ----- low3 high 4 # low 3 high 4 mid 4 ----- low4 high 4 # break lowhigh4 # 找的是靠左的那一个 low0 highlen(a)-1 def search(low,high,x): # 查找的是前一个 while (lowhigh): mid (lowhigh1)//2 # (231)//23 偏右 if (a[mid]x): lowmid else: highmid-1 print(a[low]) print(a[high]) search(low,high,10) # 查找结果10二分例题1.分巧克力根据题意转为二分二分找边长Nimport os import sys # 请在此输入您的代码 def check(d): # 检查蛋糕大小为d是否可分 num 0 for i in range(n): num(w[i]//d)*(h[i]//d) if(numk):return True else:return False h [0]*100010 w [0]*100010 n,k map(int,input().split()) for i in range(n): # 读入蛋糕大小 h[i],w[i] map(int,input().split()) L,R 1,100010 # 结尾更大防止出现边界问题 while LR: mid(LR1)//2 # 偶数中值为右值 [1,2] --2 没有则取前 if(check(mid)): Lmid else: Rmid-1 print(L) # mid(LR)//2 #偶数中值为左值 [1,2] --1 ,没有则取后 # if(check(mid)): # Lmid1 # else: # Rmid #print(L-1)更合理的写法import sys #设置递归深度 import collections #队列 import itertools # 排列组合 import heapq #小顶堆 import math sys.setrecursionlimit(300000) n,k map(int,input().split()) save [] #存放巧克力 Max1 for i in range(n): templist(map(int,input().split())) Maxmax(max(temp),Max) # 记录大巧克力边长之后用于二分 save.append(temp) def check(i): count0 for a,b in save: count(a//i)*(b//i) if countk: return True else: return False left1 rightMax while(leftright): # 找x的第一个 mid(leftright1)//2 #print(left,mid,right) #print(-*40) if check(mid): leftmid else: rightmid-1 print(left) #print(right) #print(mid) 2 10 6 5 5 6 测试结果 1 4 6 ---------------------------------------- 1 2 3 ---------------------------------------- 2 3 3 ---------------------------------------- 2 2 3 2.跳石头 根据题意转为二分二分找d开始在i(i0)位置我在跳下一步的时候去判断我这个当前跳跃的距离如果这个跳跃距离比二分出来的mid小那这就是一个不合法的石头应该移走。为什么我们二分的是最短跳跃距离已经是最短了如果跳跃距离比最短更短岂不是显然不合法是这样的吧。移走之后要怎么做先把计数器加上1再考虑向前跳啊。去看移走之后的下一块石头再次判断跳过去的距离如果这次的跳跃距离比最短的长那么这样跳是完全可以的我们就跳过去继续判断如果跳过去的距离不合法就再拿走这样不断进行这个操作直到i n1为啥是n1河中间有n块石头显然终点在n1处。这里千万要注意不要把n认为是终点实际上从n还要跳一步才能到终点。import sys import collections import itertools import heapq sys.setrecursionlimit(300000) Len,n,m map(int,input().split()) stone[] #石头i和到起点的距离 def check(d): num0 # 可以搬走的数量 pos0 # 上一块石头位置 for i in range(0,n): # 0 - n-1 作为石头下标,总共n快石头 if (stone[i]-posd): # 可以搬走 num1 else: # 不能搬走 posstone[i] if numm: # 搬走的数量小于要求值可以继续增大 return True else: return False for i in range(n): tint(input()) stone.append(t) L,R0,Len while(LR): mid(LR1)//2 if check(mid): Lmid else: Rmid-1 print(L)3.青蛙过河根据题意转为二分即跳跃距离 将所有的石头按照区间分类1步可达的石头2步可达的石头显然能通过一步走到就绝对不通过两步去走 因为石头能被踩的次数是有限的例如1234假如最大步长为3在1的时候可以一步走到4号石头但要是 从1走到2再从2走到4跟直接从岸上走到2再从2走到4没有区别因此每一次移动都必须移动到不同标号的区间去 有效的移动只有跨不同区间的移动 步长合法性判断 对于任意石头i,区间[i,ix)中的石头可被踩的总数2x 证明 岸123|456|789岸 按照有效移动理论在1时下一步只能走到4去因此想要容纳1全部的被踩次数4号的石头高度应1号而显然 想要总过河次数2x那么区间[1,3]中石头总高度2x因为出门的第一步必须要有2x次以上即[1,3]总高度2x 又因4号高度1号高度故区间[2,4]高度之和2x以此类推可以证明要想总过河次数2x任一石头编号开始长度为 步长的区间石头总高度之和2x 再按照二分法搜索答案适用二分法的特性当步长为ans时可满足题目要求ans1一定可以满足题目要求 初始解区间[1,n],不断将解区间二分寻找到能够满足题目要求的最小解 import sys import collections import itertools import heapq sys.setrecursionlimit(300000) def check(mid): for i in range(mid,n): if sum[i]-sum[i-mid] 2*x: return False return True n,x map(int,input().split()) h list(map(int,input().split())) sum[0] # 前缀和下标从1开始 temp0 for i in range(len(h)): # 前缀和 temptemph[i] sum.append(temp) L0 Rn while(LR): mid(LR)//2 if check(mid): Rmid else: Lmid1 print(L)4.实数二分一元三次方程求解送分import sys #设置递归深度 import collections #队列 import itertools # 排列组合 import heapq #小顶堆 import math sys.setrecursionlimit(300000) a,b,c,d map(float,input().split()) def f(x): return x*x*x*ax*x*bx*cd ans[] for i in range(-100,100): if f(i)0: ans.append(i) if f(i)*f(i1)0: # 在ii1内有根 li;ri1 while(r-l0.001): # 保留精度,2位小数,注意循环条件 mid(lr)/2 if f(l)*f(mid)0: rmid else: lmid ans.append(l) if f(100)0: ans.append(100) for i in ans: print({:.2f}.format(i),end )