本文主要是介绍Python算法100例-1.9 折半查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
完整源代码项目地址，关注博主私信’源代码’后可获取
- 1.问题描述
- 2.问题分析
- 3.算法设计
- 4.完整的程序
- 5.问题拓展
1．问题描述
N个有序整数数列已放在一维数组中，利用二分查找法查找整数m在数组中的位置。若找到，则输出其下标值；反之，则输出“Not be found!”。
2．问题分析
二分查找法（也叫折半查找）其本质是分治算法的一种，所谓分治算法指的是分而治之，即将较大规模的问题分解成几个较小规模的问题，这些子问题互相独立且与原问题相同，通过对较小规模问题的求解达到对整个问题的求解。当我们将问题分解成两个较小问题求解时的分治方法称为二分法。需要注意的是，二分查找法只适用于有序序列。
二分查找法的基本算法是：每次查找前先确定数组中待查的范围。假设指针low和high（low<high）分别指示待查范围的下界和上界，指针mid指示待查范围的中间位置，即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．完整的程序
程序流程图如图所示。
完整的程序如下：
%%time
# 折半查找
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 - 1else:if m > a[mid]:low = mid + 1else:k = midbreak # 一旦找到所要查找的元素便跳出循环if k >= 0:print("m = %d, index = %d" %(m, k))else:print("Not be found!")
a数组中的数据如下：
-3 4 7 9 13 45 67 89 100 180
m = 13, index = 4
CPU times: user 33.3 ms, sys: 11.6 ms, total: 44.9 ms
Wall time: 4.16 s
在上述程序中循环结束可以有两种情况，一种是在循环的判定条件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．问题拓展
在一个给定的数据结构中查找某个指定的元素，通常根据不同的数据结构应采用不同的查找方法。对于一个有序数列，除了采用二分查找法之外还可以采用顺序查找的方法。
顺序查找一般是指在线性表中查找指定的元素，其基本方法是：从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到，即查找成功；若线性表中所有的元索都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素，即查找失败。
在长度为n的线性表中查找指定元素，最好的情况是比较1次就成功，最坏的情况是比较n次，平均要比较(1+2+3+…+n)/n=(1+n)/2次。尽管顺序查找的效率低，但有些情况只能采用顺序查找的方法，如对于一个无序表进行查找。
完整的程序如下：
%%time
# 顺序查找
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 = 0while i < len(a):if m == a[i]:k = ibreak # 一旦找到所要查找的元素便跳出循环i += 1if k >= 0:print("m = %d, index = %d" %(m, k))else:print("Not be found!")
a数组中的数据如下：
-3 4 7 9 13 45 67 89 100 180
m = 13, index = 4
CPU times: user 31 ms, sys: 10.9 ms, total: 41.9 ms
Wall time: 2.38 s
对数据进行排序及查找的方法较多，理解每一种方法的思想是编程的第一步，不同方法之间的效率是不同的，在没有特别要求的情况下读者可根据自己掌握的情况进行编程。但对于一些有一定适用范围的方法，读者一定要牢记。
这篇关于Python算法100例-1.9 折半查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
