二分查找.PPT
- 格式：ppt
- 大小：921.50 KB
- 文档页数：15
下载文档原格式
合集下载
《算法案例3二分法》课件
算法定义
有序步骤
算法是一系列有序 的步骤
有限性
算法在执行过程中 会在有限步骤内终
止
确定性
算法保证经过有限 次计算后可以得到
确定的结果
算法特性
输入输出
算法具有输入和输 出
确定性
相同输入条件下， 算法的输出结果唯
一
有效性
算法解决问题的方 法必须有效
01 计算机科学
算法是计算机科学的基础
02 人工智能
● 03
第3章 二分法改进
二分法变形
二分查找的变形问题包括根据不同已知条件下的优化以及多 指针二分法的应用。这些变形能够提高算法的效率和适用性。
二分法应用
图论中的应用
优化路径搜索
贪心算法中的 应用
局部最优解
动态规划中的 应用
寻找最优解
01 LeetCode上的经典问题
二分搜索
02 实际项目中的案例
医疗领域的二分法 实践
医疗影像处理中的应用
疾病诊断模型的优化
智能化领域的二分法 实践
智能家居系统中的应用
智能机器人算法优化
二分法在游戏开 发中的应用
在游戏开发中，二分法被广泛应用于解决地图路径规划、资 源分配等问题。游戏引擎中的二分法可以提高游戏性能和体 验，策略游戏中的二分法可以优化AI决策，多人在线游戏中 的二分法能提升服务器响应速度。
《算法案例3二分法》PPT 课件
制作人：PPT创作创作 时间：2024年X月
第1章 算法概述 第2章 二分法原理 第3章 二分法改进 第4章 二分法应用拓展 第5章 实践应用案例 第6章 总结与展望
目录
● 01
第1章 算法概述
什么是算法？
数据结构查找与排序PPT课件
Step1：（初始建堆）把待排序元素保存在数组的1至n位置上, 把 这个元素集合（不包括位置0）做成一个最大堆 Step2：交换堆顶元素与当前集合的最后一个元素,然后把堆的范围 看做1至n-1（即这时候堆的最后一个元素为n-1,而非n）进行“筛 选”,再构造成一个最大堆 Step3：重复Step2,直至堆的大小为1,排序完成
第7页/共29页
一、基于选择的排 序1. 简单选择排序
2. 堆排序（Heap Sort）
1. 简单选择排序算法思想：
每一趟从当前待排序的记录中选择关键字最大（小）的记录,然后与末尾 （首）记录进行交换
算法关键部分： for (i=1; i < N; i++)
{ min = i ; for (j=i+1; j<=N; j++) if (A[j]< A[min]) ) min=j; //min是待排序列中关键字最小的记录所 在位置 if (min!=i) 交换A[i]与A[min]； }
依次比较相邻的两个记录的关键字,若两个记录是反序的(即前一个记录的关 键字大于后前一个记录的关键字),则进行交换,直到没有反序的记录为止。
冒泡排序算法分析
冒泡排序时间复杂度
◆ 最好情况(正序)：比较次数：n-1；移动次数：0；
◆ 最坏情况(逆序)： 比较次数：
n-1
∑(n-i)=
i=1
n(n-1) 2
第3页/共29页
2、已知待散列存储的关键字序列为（4,15,38,49,33,60,27,71）,哈希函数为H（ key）=keyMOD11,哈希表HT的长度为11,采用二次探测再散列法（d=12,-12,22,22,32,…）解决冲突,试构造此哈希表,并求出在等概率情况下查找成功的平均查找 长度。
第7页/共29页
一、基于选择的排 序1. 简单选择排序
2. 堆排序（Heap Sort）
1. 简单选择排序算法思想：
每一趟从当前待排序的记录中选择关键字最大（小）的记录,然后与末尾 （首）记录进行交换
算法关键部分： for (i=1; i < N; i++)
{ min = i ; for (j=i+1; j<=N; j++) if (A[j]< A[min]) ) min=j; //min是待排序列中关键字最小的记录所 在位置 if (min!=i) 交换A[i]与A[min]； }
依次比较相邻的两个记录的关键字,若两个记录是反序的(即前一个记录的关 键字大于后前一个记录的关键字),则进行交换,直到没有反序的记录为止。
冒泡排序算法分析
冒泡排序时间复杂度
◆ 最好情况(正序)：比较次数：n-1；移动次数：0；
◆ 最坏情况(逆序)： 比较次数：
n-1
∑(n-i)=
i=1
n(n-1) 2
第3页/共29页
2、已知待散列存储的关键字序列为（4,15,38,49,33,60,27,71）,哈希函数为H（ key）=keyMOD11,哈希表HT的长度为11,采用二次探测再散列法（d=12,-12,22,22,32,…）解决冲突,试构造此哈希表,并求出在等概率情况下查找成功的平均查找 长度。
从顺序查找到二分查找课件
120
j=m-1 =7
125
125
125
130 j=10
130 j=10
130
Key=65
21
i=1 21
i=1
21
56
56
mid=2 56
78 Key > a(m) 78
98
98
101 m=5 101
106 Key < a(m) 106
110
110
120
120
125
125
130 j=10 130
i=1 : j = n
i<＝j ？ Y
m=(i+j)\2
a(m)=key ?
N
key<a(m)?
Y
j=m-1
N i=m+1
课堂实践
总结：顺序查找与二分查找
顺序查找 二分查找
对数组的要求 无要求 假设数组是有序的前提
比较的次数
<=n
查找效率
低
必须是有序的
<=int(log2n)+1 高
中，故新的查找区间是左子数组a(1..m-1)中。 n 若Key>a(m) ，则要找的Key可能在mid的右子数组a(m+1..n)
中，即新的查找区间是右子表a(m+1..n) 。 n …… n 找不到时结束的条件：i > j
程序流程图
开始
输入待查找的值给变量key
N
输出“找不到” Y
输出 m
结束
从顺序查找到二分查找
查找
n 给定一个值Key，在含有n个元素的数组中 找出等于给定值Key的元素。若找到，则查 找成功，返回元素的信息或该元素在表中 的位置；否则查找失败，返回相关的指示 信息。
5.4.2 查找算法的应用 课件(34张PPT)
m
j
01 234 5 6 7 8 9 200370 430 560 585 610 790 820 932 968
01 234 5 6 7 8 9
设计算法
查找积分在[500,800]的会员
1.要进行几次(800)在积分中一定存在吗？ 可能不存在
>500
ji
200370 430 560585 610 790 820 932 968
ji 200470 630 760 800 800 800 800 800 968
j位置数<=key<i位置数
def bsearchy(s,array): i=1 j=len(array)-1 while i<=j: m=(i+j)//2
if s<=int(array[m][3]): j=m-1
else: i=m+1
ji
200470 500 500 500 500 500 650 730 968
j位置数<key<=i位置数
def bsearchz(s,array): i=1 j=len(array)-1 while i<=j: m=(i+j)//2
if s<=int(array[m][ 3]): j=m-1
else: i=m+1
jmi
01 234 5 6 7 8 9 200370 430 560585 610 790 820 932 968
01 234 5 6 7 8 9
设计算法
查找积分在[500,800]的会员
1.要进行几次二分查找？
两次二 分查找
2.500(800)在积分中一定存在吗？ 可能不存在 i 3.500(800)的积m分会不会存在多个？j 可能存在
4.3 非数值计算(二分查找)课件 -2023—2024学年高中信息技术教科版(2019)必修1
elif mid < x:
#区域中间值大于目标数
flag1 = mid + 1 #范围往右侧区域找 = 左边界后移
else:
break
print('查找次数为：',step)
任务：巧翻字典
x = int(input('请输入要查找的数据：'))
上机实践1
step = 0
#查找次数
flag1 = 1
知识探究：二分查找/折半查找
二分思想：将数列有序排列，采用跳跃的方式 查找数据。
在有n个元素的有序序列中，利用二分查找大
约需要log2n次。
n = 1000 需要10次
任务：巧翻字典 程序编写——补充程序
x = int(input('请输入要查找的数据：'))
step = 0
#查找次数
flag1 = 1
项目内容
本节我们将围绕“生活中的算法”项目，尝试用“算法的 眼睛”看待生活，用“算法的思维”去解决实际问题。
项目任务
本节任务
➢ 任务一：巧翻字典
➢ 任务二：玩转“汉诺塔”游戏
任务：巧翻字典 活动：统计查字典次数
➢ 查汉字、查单词、查成语等查字典的活动，早已成为我们学习生活的部分。假设一本 字典大约1000页，目标信息在第328页。请记录你翻页过程，和同学们比比，看谁翻 的次数最少。
二分查找的应用：找出1-1000之间的某个数
import random x = random.randint(1,1000)
while 0<x<1000: y = int(input("请输入这个数：")) if x<y: print("大了") elif x>y: print("小了") else: print("就是",x) break
算法图解（二分查找）
算法图解（⼆分查找）⼆分查找假设你要查找电话本⾥k开头的⼈⾥可能会直接滑动到中间因为你知道k在中间位置因为电话本是abcdef排序的嘛定义：⼆分查找就指从中间开始查找的逻辑做法注：# ⼆分查找必须是有序序列返回其位置# ⽆序⽆法进⾏⼆分查找返回null例如：⼆分查找： 利⽤⼆分查找每次取中间数有⼩数可以向上或向下取整数 100以内的数字最多7次可以找出来普通查找： ⽽普通查找则是从头到位遍历最好的情况是1 ⼀次找出最差是100次⼆分查找随着元素的增加并不会改变太⼤普通查找则会随元素的增加⽽增加⽐如说⼀个字典内有240000个单词普通查找最差情况：240000次出结果⼆分查找最差情况：17次出结果这就很明显的突出了⼆分算法的优势####这⾥我⽤（）括号⾥的数字代表log的下标⽤⼆分查找最多需要log（2）n步其实就是利⽤对数运算：对数运算：定义：幂运算的逆运算例如：10**2 = 100 log（10）100 = 210**3 = 1000 log（10）1000=32**5 = 32 log（2）32 = 5如果有8个元素你最多需要查找3次因为long8 = 3（2**3=8）1024个元素最多需要检查10个元素因为 1024 = 10（2**10=1024）def binary(lst, item):low = 0high = len(lst) - 1while low <= high:mid = round((low + high) / 2)guess = lst[mid]if guess == item: # 猜对了return midif guess > item:high = mid - 1 # 猜⼤了else:low = mid + 1 # 猜⼩了return Nonemy_list = [1, 3, 5, 7, 9]print(binary(my_list, 3)) # 1 返回的元素下标索引是0开始的print(binary(my_list, -1)) # None 因为不存在-1元素运⾏时间： 线性时间（linear time） 100个数字最多猜100次 40亿猜40亿次最多猜的次数等于列表的长度 对数时间（或log时间） 100个数字最多猜7次 40亿猜32次⼤O表⽰法： 简单查找每个元素需要n次运⾏时间为O（n） ⼆分查找运⾏时间为O（log（n））⼤O表⽰法计算的是操作数 O（log n）对数时间包括⼆分查找 O（n）线性时间 O（n * log n）快速排序算法 O（n**2）速度较慢排序法算法 O（n！）⾮常慢的算法⼩结： ⼆分查找⽐简单查找快的多 O（log n）⽐O（n）快，需要搜索的元素越多，前者⽐后者就快的越多 算法运⾏时间并不以秒为单位 算法运⾏时间是从其增速的⾓度度量的 算法的运⾏时间⽤⼤O表⽰法表⽰。
二分法的动画演示课件
A(30)
40 high
A(40)
要查找的数据是 key
mid=int((low+high)/2)
Key=a(mid) 找到了
Key>a(mid) low=mid+1 Key<a(mid)
思考 1
low
A(1)
A(1)
A(1)
20
·mid
A(20)
40 high
A(40)
21 low
A(21)
·30
Key=a(mid) 找到了
Key>a(mid) low=mid+1 Key<a(mid) high=mid-1
·21 22 24
low mid high
A(21) A(22) A(24)
A(40)
思考 1
low
A(1)
A(1)
A(1)
A(1) A(1)
20
·mid
A(20)
40 high
A(40)
二分查找（对分查找）
查找条件： 被查找的数据必须是有序的。
基本思想： 在有序的数据列中，首先将要查找的数据与有序数组
内处于中间位置的数据进行比较，如果两者相等，则查 找成功；否则根据数组元素的有序性，就可确定该数据 应该在数组的前半部分还是后半部分继续进行查找；在 新确定的范围内，继续按上述方法进行查找，直到找到 要查找的数据，即查找成功，或直到子表不存在，即查 找不成功。
21 low
A(21)
·30
mid
A(30)
40 high
A(40)
21 Low
·25 29 mid high
A(21) A(25) A(29)
40 high
A(40)
要查找的数据是 key
mid=int((low+high)/2)
Key=a(mid) 找到了
Key>a(mid) low=mid+1 Key<a(mid)
思考 1
low
A(1)
A(1)
A(1)
20
·mid
A(20)
40 high
A(40)
21 low
A(21)
·30
Key=a(mid) 找到了
Key>a(mid) low=mid+1 Key<a(mid) high=mid-1
·21 22 24
low mid high
A(21) A(22) A(24)
A(40)
思考 1
low
A(1)
A(1)
A(1)
A(1) A(1)
20
·mid
A(20)
40 high
A(40)
二分查找（对分查找）
查找条件： 被查找的数据必须是有序的。
基本思想： 在有序的数据列中，首先将要查找的数据与有序数组
内处于中间位置的数据进行比较，如果两者相等，则查 找成功；否则根据数组元素的有序性，就可确定该数据 应该在数组的前半部分还是后半部分继续进行查找；在 新确定的范围内，继续按上述方法进行查找，直到找到 要查找的数据，即查找成功，或直到子表不存在，即查 找不成功。
21 low
A(21)
·30
mid
A(30)
40 high
A(40)
21 Low
·25 29 mid high
A(21) A(25) A(29)
数据结构教学课件7-02二分查找
1、基本思想：设R[low...high]是当前的查找区间。
（1）首先确定该区间的中点位置：mid=[(low+high)/2]; （2）然后将待查找的K值与R[mid].key比较：若相等，则查找成功并返回
此位置，否则须确定新的查找区间，继续二分查找，具体方法如下： ①若R[mid].key>K，则由表的有序性可知R[mid…n]. key均大于K，因此若
low=mid+1;//继续在R[mid+1...high]中查找 } return 0;//当low>high时查找区间为空，查找失败 }
说明
➢ 从初始的查找区间R[1...n]开始， 每经过一次与当前查找区间的中点 位置上结点关键字的比较，若相等 则查找成功，否则当前查找区间就 缩小一半。重复这一过程直至找到 关键字为K的结点，或者当前查找 区间为空，即查找失败为止。
表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表 R[1…mid-1]中，故新的查找区间是左子表R[1...mid-1]； ②若R[mid].key<K，类似地，则新的查找区间是右子表R[mid+1…n]。下 次在新的查找区间进行查找。
二分查找
2、具体算法
int BinSearch(SeqList R,KeyType K) {//在有序表R[1...n]中进行二分查找，成功时返回结点位置，失败时返回零
H
下标 第1次比较 第2次比较 第3次比较来自123
4
5
6
7
8
9
10
11
K
[05
13
19
21
37
56
64
75
80
88
（1）首先确定该区间的中点位置：mid=[(low+high)/2]; （2）然后将待查找的K值与R[mid].key比较：若相等，则查找成功并返回
此位置，否则须确定新的查找区间，继续二分查找，具体方法如下： ①若R[mid].key>K，则由表的有序性可知R[mid…n]. key均大于K，因此若
low=mid+1;//继续在R[mid+1...high]中查找 } return 0;//当low>high时查找区间为空，查找失败 }
说明
➢ 从初始的查找区间R[1...n]开始， 每经过一次与当前查找区间的中点 位置上结点关键字的比较，若相等 则查找成功，否则当前查找区间就 缩小一半。重复这一过程直至找到 关键字为K的结点，或者当前查找 区间为空，即查找失败为止。
表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表 R[1…mid-1]中，故新的查找区间是左子表R[1...mid-1]； ②若R[mid].key<K，类似地，则新的查找区间是右子表R[mid+1…n]。下 次在新的查找区间进行查找。
二分查找
2、具体算法
int BinSearch(SeqList R,KeyType K) {//在有序表R[1...n]中进行二分查找，成功时返回结点位置，失败时返回零
H
下标 第1次比较 第2次比较 第3次比较来自123
4
5
6
7
8
9
10
11
K
[05
13
19
21
37
56
64
75
80
88
《折半查找法》课件
实际应用广泛
在数据库、搜索引擎、物流配送 等领域，快速准确的查找是实现 高效服务的关键。
折半查找法的概念
• 定义：折半查找法，又称二分查找法，是一种在有序数组中查 找某一特定元素的搜索算法。搜索过程从数组的中间元素开始 ，如果中间元素正好是要查找的元素，则搜索过程结束；如果 某一特定元素大于或者小于中间元素，则在数组大于或小于中 间元素的那一半中查找，而且跟开始一样从中间元素开始比较 。如果在某一步骤数组为空，则代表找不到。这种搜索算法每 一次比较都使搜索范围缩小一半。
感谢观看
与线性查找法相比，折半查找 法在数据量大的情况下具有明 显优势。
需要快速查找的场景
在某些对时间要求较高的场景中 ，如实时交易系统、在线游戏等
，需要快速查找数据。
折半查找法能够在较短时间内找 到目标数据，满足快速查找的需
求。
与其他查找算法相比，折半查找 法具有较高的查找速度。
二分搜索的应用场景
二分搜索是折半查找法的另一种表述方式，适用于有序数组的查找。
线性二分查找的变种
在有序数组中，从中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或 小于中间元素，则在数组大于或小于中间元素的那一半中查找，但这一次从那一半的起始位置开始比 较。
多重二分查找
多重二分查找是指在一次二分查找过程中，对多个有序数组 进行查找的方法。通过将多个有序数组按照某种规则进行组 合，可以大大提高查找效率。
在需要频繁进行查找操作的场景中，如搜索引擎、数据分析等，二分搜索能够提高 查找效率。
二分搜索适用于任何有序数据集，只要能够确定数据集的左边界和右边界即可。
05
折半查找法的优化与改进
二分查找的变种
线性二分查找
在数据库、搜索引擎、物流配送 等领域，快速准确的查找是实现 高效服务的关键。
折半查找法的概念
• 定义：折半查找法，又称二分查找法，是一种在有序数组中查 找某一特定元素的搜索算法。搜索过程从数组的中间元素开始 ，如果中间元素正好是要查找的元素，则搜索过程结束；如果 某一特定元素大于或者小于中间元素，则在数组大于或小于中 间元素的那一半中查找，而且跟开始一样从中间元素开始比较 。如果在某一步骤数组为空，则代表找不到。这种搜索算法每 一次比较都使搜索范围缩小一半。
感谢观看
与线性查找法相比，折半查找 法在数据量大的情况下具有明 显优势。
需要快速查找的场景
在某些对时间要求较高的场景中 ，如实时交易系统、在线游戏等
，需要快速查找数据。
折半查找法能够在较短时间内找 到目标数据，满足快速查找的需
求。
与其他查找算法相比，折半查找 法具有较高的查找速度。
二分搜索的应用场景
二分搜索是折半查找法的另一种表述方式，适用于有序数组的查找。
线性二分查找的变种
在有序数组中，从中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或 小于中间元素，则在数组大于或小于中间元素的那一半中查找，但这一次从那一半的起始位置开始比 较。
多重二分查找
多重二分查找是指在一次二分查找过程中，对多个有序数组 进行查找的方法。通过将多个有序数组按照某种规则进行组 合，可以大大提高查找效率。
在需要频繁进行查找操作的场景中，如搜索引擎、数据分析等，二分搜索能够提高 查找效率。
二分搜索适用于任何有序数据集，只要能够确定数据集的左边界和右边界即可。
05
折半查找法的优化与改进
二分查找的变种
线性二分查找