二分法
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
- 确定边界的变化,根据定义的第二句话,写出代码如下
3.整数域二分
m i d = ( l e f t + r i g h t ) / / 2 mid = (left+right) // 2 mid=(left+right)//2
m i d = l e f t + ( r i g h t − l e f t ) / / 2 (防止溢出) mid = left + (right-left) // 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
- 代码执行完毕后, l e f t = r i g h t left=right 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
- 当 l e f t = r i g h t left=right 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
示例:
[NOIP2001 提高组] 一元三次方程求解 - 洛谷
思路分析:
(二分法是建立在枚举的基础上进行的优化,所以此类问题往往是先考虑枚举,再根据二分法对算法进行优化)枚举**根的值域中的每一个整数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]属于哪个区间,即满足小于左区间最大值属于右区间,大于右区间最大值属于左区间
思路与算法:
(图片来源于leetcode)
其中横轴表示数组元素的下标,纵轴表示数组元素的值。图中标出了最小值的位置,是我们需要查找的目标。
我们考虑数组中的最后一个元素 x:在最小值右侧的元素(不包括最后一个元素本身),它们的值一定都严格小于 x;而在最小值左侧的元素,它们的值一定都严格大于 x。因此,我们可以根据这一条性质,通过二分查找的方法找出最小值。
在二分查找的每一步中,左边界为 low 右边界为 high,区间的中点为 pivot,最小值就在该区间内。我们将中轴元素 nums[pivot]与右边界元素 nums[high]进行比较,可能会有以下情况:
第一种情况是 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直接错过了
总结: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.最小值最大化
示例:
跳石头
519. 跳石头 - AcWing题库
思路分析:
在 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)//2
if 满足条件:
left=mid
else:
right=mid-1
-
找最大值的最小化:相当于每找到一个合法值就限定右边界,为向右看齐:
mid=left+(right-left)//2
if 满足条件:
right=mid
else:
left=mid+1
3.最大值最小化
示例:
青蛙过河
思路分析:
- 因为要使跳跃距离≤d,又要使d最小,为最大值的最小化,则考虑二分
-
首先要理解一个问题:
往返累计2x次等效于单独去2x次
原因:实际上转化一下,怎么去就怎么回,所以其实就是和去2x次一模一样
-
接下来,考虑对跳跃距离d在区间内进行二分:
l l 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)
7.总结
本篇主要讲解了二分法的一些表示及其用法,同样后面也有一些相应的实例,后续还会更新其他常见的算法,如果有错误请欢迎指正~~,感谢!!!
文章来源:https://www.toymoban.com/news/detail-703982.html
觉得本篇有帮助的话, 就赏个三连吧~
文章来源地址https://www.toymoban.com/news/detail-703982.html
到了这里,关于【算法】—二分法详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!