行业知识
【算法】—二分法详解
二分法
文章目录
- 二分法
- 1.二分法
- 2.引论:猜数游戏
- 3.整数域二分
- 1、在单调递增序列中找 x 或者 x 的后继
- 2、在单调递增序列中查找 x 或者 x 的前驱
- 3.简易二分模板
- 4.浮点数二分
- 5.边界二分
- 1.旋转数组
- 2.开闭区间
- 6.二分法的应用
- 1.优化时间复杂度
- 2.最小值最大化
- 3.最大值最小化
- 7.���结
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 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]
上一篇:私服怎么上传服务器