栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

100个python算法超详细讲解:折半查找

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

100个python算法超详细讲解:折半查找

1.问题描述
N个有序整数数列已放在一维数组中,利用二分查找法查找整数m在数组中的
位置。若找到,则输出其下标值;反之,则输出“Not be found!”。
2.问题分析
二分查找法(也叫折半查找)其本质是分治算法的一种,所谓分治算法指的
是分而治之,即将较大规模的问题分解成几个较小规模的问题,这些子问题互相
独立且与原问题相同,通过对较小规模问题的求解达到对整个问题的求解。当我
们将问题分解成两个较小问题求解时的分治方法称为二分法。需要注意的是,二
分查找法只适用于有序序列。
二分查找法的基本算法是:每次查找前先确定数组中待查的范围。假设指针
low和high(low 中间位置,即mid=(low+high)/2,把m与中间位置(mid)上元素的值进行比
较。如果m的值大于中间位置上元素的值,则下一次的查找范围放在中间位置之
后的元素中;反之,下一次的查找范围放在中间位置之前的元素中。直到
low>high,查找结束。
3.算法设计
N个有序数因存放在数组中,根据数组下标的取值范围可知指针low和high的
初值分别为0和N-1。除了3个指针变量low、high、mid之外,还需要一个变量假设
为k来记录下标,利用变量k的值来判断整数m是否在所给出的数组中。下面我们
用示意图来表示二分查找的过程。
假设一维数组中存储的有序数列为:5 13 19 21 37 56 64 75 80 88 92,要查找
的整数m为21。根据二分查找方法可知指针low和high最初分别指向元素5和92,由
mid=(low+high)/2知,指针mid指向元素56。示意如下:

 变量m所代表的整数21与指针mid所指的元素56进行比较,21小于56,根据二
分查找算法可知,查找范围现在缩小到指针mid所指元素的前面,即从5到37的范
围。指针high原来指向下标为N-1的元素,现在指向下标为mid-1的元素,接着重
新计算指针mid所指元素的下标。示意如下:

再次进行比较,21大于19,现在比较范围再次转移到mid所指元素的后面,
low元素所指元素下标由0变为mid+1。示意如下:

 

当前mid所指元素的值为21,与要查找的整数值相同,故查找成功,所查元素
在表中的序号等于指针mid的值。
查找不成功的过程请读者自己完成。

4.完整的程序
程序流程图如图1.17所示。
完整的程序如下:

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 折半查找
if __name__ == "__main__":
	a = [-3, 4, 7, 9, 13, 45, 67, 89, 100, 180]
	low = 0 # 数组上界
	high = len(a) - 1 # 数组下界
	k = -1 # 记录下标
	print("a数组中的数据如下:")
	for i in a:
		print(i, end=" ") # 输出数组中原数据序列
		print()
		m = int(input("Enter m = : ")) # 变量m为要查找的整数
		while low <= high: # 继续查找的控制条件
			mid = (low + high) // 2 # 变量mid为数组序列的中间位置
			if m < a[mid]:
				high = mid - 1
			else:
				if m > a[mid]:
					low = mid + 1
				else:
					k = mid
					break # 一旦找到所要查找的元素便跳出循环
					if k ≥ 0:
						print("m = %d, index = %d" %(m, k))
					else:
						print("Not be found!")### unterminated keywords ###

 

在上述程序中循环结束可以有两种情况,一种是在循环的判定条件low≤high
不成立的情况下跳出循环,此时可知查找不成功。在查找不成功的情况下if
m>a[mid]语句的else语句块是不执行的,所以变量k的值不变仍为初值-1。第二种
结束循环的情况是由于执行了break语句而跳出循环,在此情况下,变量k的值由-1
变成了一个大于等于0的数,即指针mid所指元素的下标值。所以在最后用选择结
构来判定k的值,从而确定整个查找过程是否成功。
补充知识点:

(1)continue语句
continue语句的格式为:

continue


continue语句用于Python的循环语句中,作为循环体的一部分。在程序执行
时,一旦遇到了continue语句,则立即结束本次循环,即跳过循环体中continue后
面尚未执行的语句,接着进行是否继续循环的条件判定。
(2)break语句
break语句的格式如下:

break


break语句用于while循环和for循环中,用来终止循环语句,即使循环条件中没
有False条件或序列还没有遍历完,也会停止执行循环语句。
如果使用嵌套循环,break语句就会停止执行最深层的循环,并开始执行下一
行代码。
continue语句和break语句的区别如下:
·continue只是结束本次循环,不再执行循环体中continue后面的其余语句,并
不是终止当前循环。
·当遇到break语句时,无论执行什么条件,都跳出这个循环。 

5.运行结果
在PyCharm下运行程序,结果如图1.18所示。

6.问题拓展
在一个给定的数据结构中查找某个指定的元素,通常根据不同的数据结构应
采用不同的查找方法。对于一个有序数列,除了采用二分查找法之外还可以采用
顺序查找的方法。
顺序查找一般是指在线性表中查找指定的元素,其基本方法是:从线性表的
第一个元素开始,依次将线性表中的元素与被查元素进行比较,若相等则表示找
到,即查找成功;若线性表中所有的元索都与被查元素进行了比较但都不相等,
则表示线性表中没有要找的元素,即查找失败。
在长度为n的线性表中查找指定元素,最好的情况是比较1次就成功,最坏的
情况是比较n次,平均要比较(1+2+3+…+n)/n=(1+n)/2次。尽管顺序查找的效率
低,但有些情况只能采用顺序查找的方法,如对于一个无序表进行查找。
完整的程序如下:

#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @desc: 折半查找
if __name__ == "__main__":
	a = [-3, 4, 7, 9, 13, 45, 67, 89, 100, 180]
	k = -1 # 记录下标
	print("a数组中的数据如下:")
	for i in a:
		print(i, end=" ") # 输出数组中原数据序列
		print()
		m = int(input("Enter m = : ")) # 变量m为要查找的整数
		i = 0
		while i < len(a):
			if m == a[i]:
				k = i
				break # 一旦找到所要查找的元素便跳出循环
				i += 1
				if k >= 0:
					print("m = %d, index = %d" %(m, k))
				else:
					print("Not be found!")

 对数据进行排序及查找的方法较多,理解每一种方法的思想是编程的第一
步,不同方法之间的效率是不同的,在没有特别要求的情况下读者可根据自己掌
握的情况进行编程。但对于一些有一定适用范围的方法,读者一定要牢记。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/893579.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号