二分法详解
目录1.二分法
在计算机科学中，二分查找算法也称折半搜索算法，对数搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半，时间复杂度是log(n)
- 一是有序数组（这里可能是整体有序比如[1,2,3,4,5]，也有可能是局部有序比如[4,5,1,2,3]），
- 二是特定元素（也有可能是满足特定的条件）。由定义我们大概就知道了二分法的应用场景，在有序数组中找特定值都可以考虑用二分法
二分法的步骤：
我们要确定一个区间[L，R]我们要找到一个性质（由题目条件决定），并且该性质满足一下两点：
①满足二段性 ②答案是二段性的分界点
我们要在一组升序的数组找一个数的下标，那我们肯定是先拿中间的与他进行比较，比较大小的判断，其实就相当于是这个性质，且这个性质满足二段性，将大于和小于我们要查找的值分为两段，而我们的查找结果就是分界点
二分法的使用条件：
①上下界确定 ②区间内有序（也可以是局部有序）
二分法的目的：
二分查找用于在多条记录中快速找到待查找的记录，它的思想是：每次将查找的范围缩小一半，直到最后找到记录或者找不到记录返回
2.引论：猜数游戏
示例1：
一个 [1, 100] 内的数字，只需猜 7 次：
>50? 是。[1, 100] 二分，中位数 50，下一步猜 [51, 100]
>75? 否。[51, 100] 二分，中位数 75，下一步猜 [51, 75]
>63? 否。[51, 75] 二分，...
>56? 否。[51, 63] 二分，
>53? 是。
=54? 是。
这个数是 54
模板：
def bin_search(nums)
low, high = 0, len(nums) - 1
while low <= high:
mid = (high - low) // 2 + low
if num[mid] == target:
return mid
elif num[mid] > target:
high = mid - 1
else:
low = mid + 1
# 未找到目标值
return -1
思路分析：
二分法题目都可以分下面三步：
- 确定是否满足二分法的使用条件 ，有序数组与查找特定元素，题目中a有序，查找的是指定元素test，满足条件
- 确定特定元素test，如：a[pos]=test
- 确定边界的变化，根据定义的第二句话，写出代码如下
low, high = 0, len(nums) - 1
while low <= high:
mid = (high - low) // 2 + low
if num[mid] == target:
return mid
elif num[mid] > target:
high = mid - 1
else:
low = mid + 1
# 未找到目标值
return -1
3.整数域二分
mid = (left+right) // 2
mid = left + (right-left) // 2 （防止溢出）
1、在单调递增序列中找 x 或者 x 的后继
- 在单调递增数列 a[ ] 中查找某个数 x，如果数列中没有 x，找比它大的下一个数
- a[mid]>=x 时：x 在 mid 的左边，新的搜索区间是左半部分，left不变，更新 right= mid
- a[mid]<x 时：x 在 mid 的右边，新的搜索区间是半部分，right不变，更新 left=mid+1
- 代码执行完毕后，left=right，两者相等，即答案所处的位置
def bin_search(a,n,x): #在数组a中找数字x，返回位置
left=0
right=n
while left<right:
mid=left+(right-left)//2
if a[mid]>=x:
right=mid
else:
left=mid+1
#print('[',left,right,']') #打印猜数游戏的过程
return left
2、在单调递增序列中查找 x 或者 x 的前驱
- 在单调递增数列 a[ ] 中查找某个数 x，如果数列中没有 x，找比它小的前一个数
- a[mid] <= x时，x 在 mid 的右边，新的搜索区间是右半部分，所以 right 不变，更新 left=mid
- a[mid] > x时，x 在 mid 的左边，新的搜索区间是左半部分，所以left不变，更新 right=mid-1
- 当left=right时，得到结果
def bin_search(a,n,x): #在数组a中找数字x，返回位置
left=0
right=n
while left<right:
mid=left+(right-left+1)//2
if a[mid]<=x:
left=mid
else:
right=mid-1
#print('[',left,right,']') #打印猜数游戏的过程
return left
总结：
1.找后继——向右对齐，mid = (left+right) // 2 即为将mid尽可能向下取，不超过目标数字，同时，尽可能保证右端不动（左端和右端相等时，即为后继）
a[mid]≥x : right=mid（右定）
a[mid]<x : left=mid+1
2.找前驱——向左对齐，mid=left+(right-left+1)//2 即为将mid尽可能向上取，超过目标数字，同时，尽可能保证左端不动（右端和相等时，即为前驱）
a[mid]≤x : left=mid（左定）
a[mid]>x : right=mid-1
3.简易二分模板
假设：L指向check()=True的部分（≤目标值），R指向check()=False的部分（＞目标值），假设可以根据题目需要来确定
二分完成后，L和R分别指向所属区域的临界位置（终止条件:l+1=r）
注意：左端点和右端点的初始化要定义在范围外，l, r = -1, n + 1
图解：
标准解题模板：
def check():
**# check为题目中判断条件**
pass
def bin_search(a, n, x):
l, r = -1, n + 1
while l + 1 != r:
mid = (l+r) // 2
if check(mid):
l = mid
else:
r = mid
return (l or r) # 选取需要的部分进行返回
模板分析：
- 左右指针均指向数组外，这样移动时直接使 l,r=mid即可——相当于自动完成了+1和-1的操作
- 返回左边界，则当≤目标值时移动 l ; 返回右边界，则当≥目标值时移动 r
- 终止条件为r=l+1 ——这里相当于左闭右开，即此时区间内只有left对应的元素
示例：
套用这个模板把区间划分成≤5和＞5两块，返回左边界：5的最后一个的下标
# 把边界划分成≤5和＞5两块
def bin_search2(a,n,x):
l,r = -1,n+1
while l + 1 != r:
mid = (l+r)//2
if a[mid]<=x:
l = mid
else:
r = mid
return l # 返回左边界
a = [1,2,2,3,5,5,5,6,7]
print(bin_search2(a,len(a),5)) # 6
若想返回5的第一个的下标，把区间划分成＜5和≥5，返回右边界r，修改部分代码即可：
# 将上面的代码中间修改成这部分代码
if a[mid]>=x:
r = mid
else:
l = mid
return r # 返回右边界
总结：
- 若想保留左边界，则判断条件时，当nums[mid]==x时就要移动左指针left=mid
- 若想保留右边界，则判断条件时，当nums[mid]==x时就要移动右指针right=mid
4.浮点数二分
浮点数二分不需要考虑边界，往往是给定一个精度范围，让你在精度范围中去找到这个数
step：
1.确定eps:当两数差小到一定程度是则可认为找到数
一般求到题目要求的精度再加两个精度，否则特殊案例精度不够通不过
2.取中间值:double mid=l+（r-l）/2 ——注意这里不是整除
3.二分法：
eps=0.0001 #精度，如果用for，可以不要eps
while right-left>eps:
#for i in range(100):
mid=left+(right-left)/2
if check(mid): **# 判定是否满足条件**
right=mid
else:
left=mid
这里left和right均更新为mid，因为存在精度，而一般的整数域二分精度可以默认为0
示例：
思路分析：
（二分法是建立在枚举的基础上进行的优化，所以此类问题往往是先考虑枚举，再根据二分法对算法进行优化）枚举根的值域中的每一个整数x（-100<=x<=100），由于根与根之差的绝对值>=1，因此设定搜索区间[l，r]，其中l=x，r=x+1——（设置二分的区域往往是一个难点，由题目条件而定）
（0）特判：判断最右端（100）是否为f（x）的根；
（1）若f（l）==0，则右端点l为f（x）的根；
这里要注意，只选择判断左端是因为，若右端也判断，则会在下一个区间再次判断，造成重根
（2）若f（l）*f（r）>0，则确定根x不在区间[l，r]内，设定[r，r+1]为下一个搜索区间；
（3）若f（l）*f（r）<0，则确定根x在区间[l，r]内：
如果确定根在区间[l，r]内的话（f（l）*f（r）<0），如何在该区间找到根的确切位置，采用二分法，将区间[l，r]分成左右两个子区间：左子区间[l，x]和右子区间[x，r]：
- 若f（l）*f（x）<=0，则确定根在左子区间[l，x] 内，将x设为该区间的右指针（r=x），继续对左子区间进行对分；
- 若f（l）*f（x）>0，则确定根在右子区间（x，r] 内，将x设为该区间的左指针（l=x），继续对右子区间进行对分；
上述对分过程一直进行到区间的间距满足精度要求为止（r-l<0.0001），此时确定l为f（x）的根
枚举+二分：
# fx表达式
def f(x):
fx=a*x**3+b*x**2+c*x+d
return fx
eps=0.001
a,b,c,d=map(float,input().split())
res=[]
# 1.枚举每一个小区间
for i in range(-100,100):
l,r=i,i+1
y1,y2=f(l),f(r)
# 1.右端为零点
if y1==0:
res.append(l)
# 2.区间内有零点——不在两端
if y1*y2<0:
# 二分法
while r-l>eps:
mid=l+(r-l)/2 # 分左右区间
if f(mid)*y1>=0:
l=mid
else:
r=mid
res.append(l)
# 4.剪枝优化
if len(res)>=3:
break
# 特判
if f(100)==0:
res.append(100)
# 输出小数点后两位数字
for i in range(3):
**# print('%.2f'%res[i],end=' 'if i!=2 else '')**
print("{:.2f}".format(res[i]),end=' 'if i!=2 else '')
-
补充：两种常用保留小数点后两位的方式：
print(”{:.2f}”.format(num))print(”%.2f”.%num)
5.边界二分
数组原本整体有序，之后围绕某一旋转点变成了局部有序，旋转点即为边界点
1.旋转数组
示例：
假设按照 升序排序 的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ，找到其中最小元素
规则：
数组 [a[0], a[1], a[2], ..., a[n-1]] **旋转一次 的结果为**
数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]
输入：nums = [4,5,6,7,0,1,2]
输出：0
思路分析：
-
确定是否满足二分法的使用条件：前面数组都是整体有序，现在变成局部有序了，target是求最小元素，满足二分条件
-
确定特定元素target的伪代码，这题target是唯一个满足小于后一个数的（未旋转作为特殊情况），在图中为nums[4]<nums[3] ——将target抽象即为nums[n-1]<nums[n]，未旋转直接返回nums[0]
-
确定边界：局部有序数组，先看数组的特点是什么，如果 以旋转点为界分为左右俩个区间，4是左边区间的最小值，2是右边区间的最大值，那么根据这俩个条件就可以确定nums[mid]属于哪个区间，即满足小于左区间最大值属于右区间，大于右区间最大值属于左区间
思路与算法
其中横轴表示数组元素的下标，纵轴表示数组元素的值。图中标出了最小值的位置，是我们需要查找的目标。
我们考虑数组中的最后一个元素 x：在最小值右侧的元素（不包括最后一个元素本身），它们的值一定都严格小于 x；而在最小值左侧的元素，它们的值一定都严格大于 x。因此，我们可以根据这一条性质，通过二分查找的方法找出最小值。
在二分查找的每一步中，左边界为 low 右边界为 high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 nums[pivot]与右边界元素 nums[high]进行比较，可能会有以下情况：（图像来源于leetcode）
第一种情况是 nums[pivot]<nums[high]：
如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分
第二种情况是 nums[pivot]>nums[high]：
如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。
第三种情况是 nums[pivot]=nums[high]：
由于数组不包含重复元素，并且只要当前的区间长度不为 1，pivot就不会与 high重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]=nums[high]的情况
class Solution:
def findMin(self, nums: list[int]) -> int:
if nums[0]<nums[1]:
return nums[0]
low=0
high=len(nums)-1
while low<high:
mid=low+(high-low)//2
if nums[mid]<nums[high]:
high=mid
else:
left=mid+1
return nums[left]
2.开闭区间
真正影响的是中间那个数字（mid）到底该不该加入下一次的查找中，也就是边界问题
二分法最重要的两个问题：
①while循环中 left 和 right 的关系，到底是 left <= right 还是 left < right
②迭代过程中 middle 和 right 的关系，到底是 right = middle - 1 还是 right = middle
1、每次查找区间在[left, right]，左闭右闭
① while(left <= right) 因为当(left == right)这种情况发生的时候，得到的结果是有意义的；左闭右闭对于区间内只有一个值也是有意义的
② if(nums[middle] > target)， right 要赋值为 middle - 1， 因为当前的 nums[middle] 一定不是 target ，需要把这个 middle 位置上面的数字丢弃，那么接下来需要查找范围就是[left,middle - 1]
def search(self, nums: List[int], target: int) -> int:
low, high = 0, len(nums) - 1
while low <= high:
mid = (high - low) // 2 + low
if num[mid] == target:
return mid
elif num[mid] > target:
high = mid - 1
else:
low = mid + 1
# 未找到目标值
return -1
2、每次查找区间在[left, right），左闭右开
①while(left < right)，因为左闭右开对于区间内只有一个值是没有意义的
②if(nums[middle] > target)， right = middle ，因为当前的 nums[middle] 是大于 target 的，不符合条件,不能取到 middle，并且区间的定义是 [left, right)，刚好区间上的定义就取不到 right, 所以 right 赋值为 middle
def search(self, nums: List[int], target: int) -> int:
low, high = 0, len(nums)
while low < high: # 区别1
mid = (high - low) // 2 + low
if num[mid] == target:
return mid
elif num[mid] < target:
low = mid + 1
else:
high = mid # 区别2
# 未找到目标值
return -1
如要查找的元素为3，将right = mid写成了right = mid - 1那么就会出现如下错误，3直接错过了
.gif)
总结：Right = nums.length or Right =nums.length-1
情况1：Right = nums.length ; while(left < right)
这种情况下，每一次二分取值mid后，判断nums[mid]，如果nums[mid] > target,那么更新右边界时，必须注意，此时Right = mid;（相当于右边为开区间）
防止出现[target , mid , right]; 更新Right = mid-1;会跳出循环外，返回值为-1的情况。
情况2：Right = nums.length-1 ; while(left <= right)
这种情况下，每一次二分取值mid后，判断nums[mid]，如果nums[mid] > target,那么更新右边界时，必须注意，此时Right = mid - 1 ;（相当于右边为闭区间）
防止出现left == Right(如果为right=mid),一直在循环内死循环问题
6.二分法的应用
1.优化时间复杂度
思路分析：
一个个试边长 d 太慢了，现在使用二分，按前面的“猜数游戏”的方法猜 d 的取值，即转化为判断对应边长下长，宽均满足条件的巧克力数是否满足条件
暴力法需要做 d 次 check()， 用二分法，只需要做 O(logd) 次 check()，总复杂度 O(nlogd)
**d∈[1，10^5]**
# 检查半径是否满足
def check(d):
cnt=0
for i in range(n):
cnt+=(w[i]//d)*(h[i]//d) **# 长，宽均要满足**
if cnt>=k:
return 1
else:
return 0
w=[0]*100010
h=[0]*100010
n,k=map(int,input().split())
for i in range(n):
w[i],h[i]=map(int,input().split())
l=0
r=100010-1
**# 找前驱**
while l<r:
mid=l+(r-l+1)//2
if check(mid)!=0:
l=mid # 左对齐
else:
r=mid-1
print(l)
2.最小值最大化
示例：
思路分析：
在 n 块岩石中移走 m 个石头，有很多种移动方法。在第 i 种移动方法中，剩下的石头之间的距离，有一个最小距离 ai
在所有移动方法的最小距离 ai 中，问最大的 ai 是多少。在所有可能的最小值中，找最大的那个，就是 “最小值最大化”。
如果用暴力法找所有的组合，在 n 块岩石中选 m 个石头的组合情况太多，显然会超时
二分思路：不去找搬走石头的各种组合，而是给出一个距离d，检查能不能搬走 m 块石头而得到最短距离 d，即转化为判断对应距离下可以搬走的石头数是否满足条件。把所有的 d 都试一遍，肯定能找到一个最短的d，用二分法找这个 d 即可
-
左指针指向起点，右指针指向终点，进行二分查找得到mid（枚举的最短距离）
-
对每一个枚举的mid(d)进行判断：
- 先令pos为起点，遍历每一个点——贪心：保证每次操作都是局部最优，最终满足全局最优
- 如果这个点到pos的距离小于d，则删去这个石头，删去石头数cnt+=1
- 如果这个点到pos的距离大于等于d，则将pos更新为该石头
- 最后判断删去石头数是否超过了限定值
d∈[1，总长]
二分+贪心：
# 3.判断距离的合法性
def check(d):
pos=stone[0]
cnt=0
for i in range(1,n+1):
# 1.如果当前石头距离pos的距离小于给定的d
if stone[i]-pos<d:
cnt+=1
else:
pos=stone[i]
if cnt<=m:
return 1
else:
return 0
l,n,m=map(int,input().split())
# 1.构造stone 表示相较于起点的距离
stone=[0]*(n+2)
stone[0]=0
stone[n+1]=l
for i in range(1,n+1):
stone[i]=int(input())
# 2.对可能的距离二分查找---最小值最大化
l,r=0,l
while l<r:
mid=l+(r-l+1)//2
if check(mid)!=0:
l=mid # 限定最小左边界
else:
r=mid-1
print(l)
二分法模板题——最小最大化问题：
-
找最小值的最大化：相当于每找到一个合法值就限定左边界，为向左看齐：
mid=left+(right-left+1)//2if 满足条件:left=midelse:right=mid-1 -
找最大值的最小化：相当于每找到一个合法值就限定右边界，为向右看齐：
mid=left+(right-left)//2if 满足条件:right=midelse:left=mid+1
3.最大值最小化
示例：
思路分析：
- 因为要使跳跃距离≤d，又要使d最小，为最大值的最小化，则考虑二分
-
首先要理解一个问题：
往返累计2x次等效于单独去2x次
原因：实际上转化一下，怎么去就怎么回，所以其实就是和去2x次一模一样
-
接下来，考虑对跳跃距离d在区间内进行二分：
l 指向最小跳跃距离为1，r 指向最大跳跃距离为n（总宽度）
①若mid合法——即能跳过去，则减少跳跃能力
②若mid不合法——即跳不过去，则增加跳跃能力
-
最关键的是判断合法性的check函数：
-
首先，要考虑青蛙应该怎么跳过去，由贪心，青蛙每次都跳自己能力极限的距离为最优，这样才尽可能保证让石头剩下的高度足够
-
其次，考虑怎么判断合法性：
-
第一种做法：可以暴力枚举，即每一个点和下一个目标位置点，下一个目标位置点可以用二分查找
-
第二种做法：
充要条件：
所有长度为 mid 的区间的和都大于等于 2x <—>则一定能走2x次
思路：由于往返可以等效，我们可以看作是2x只青蛙同时在过河，若划分为以mid为长度的k个区间，则所有青蛙必定会经过各个mid区间1次，即每个区间都会被走过2x次，所以要使都能走过去，一定要让每一个mid区间内高度和大于2x
实现：所以，用sum记录每一个点到起点之间的高度总和，当给定一个mid时，以i为终点（mid≤i≤总长），区间长为mid，则该区间内的高度和即为sum[i]-sum[i-mid]，遍历每一个区间，判断其是否大于2x即可，时间复杂度为O（n）
-
def check(d):
for i in range(mid,n): # 遍历以i-mid为起点的每一个区间
if sum[i]-sum[i-mid]<2*x: # 若存在区间长度小于2x 跳不过去
return 0
return 1
n,x=map(int,input().split())
# 记录石头的高度
s_high=list(map(int,input().split()))
# 记录区间石头的高度和 起点高度和为0
sum=[0,s_high[0]]
for i in range(1,len(s_high)):
sum.append(s_high[i]+sum[i])
# 二分法
l,r=1,n # 跳跃能力区间
while l<r:
mid=l+(r-l)//2
if check(mid):
r=mid # 能跳过去 减少跳跃能力
else:
l=mid+1 # 跳不过去 增加跳跃能力
print(r)