Python实现二分法搜索
5星 · 超过95%的资源 7 浏览量
2020-12-20
19:32:30
上传
评论
收藏 255KB PDF 举报 
Python实现二分法搜索实现二分法搜索
Python实现二分法搜索实现二分法搜索
二分法是一种效率比较高的搜索方法，时间复杂度为 O(log2n) 。
假设有一个1~100之间的数字，你来猜这个数是多少，每猜一次可以得到三种回答：正确、大了或小了。如何保证用最少的次
数猜对？很多人会想到先猜50，如果猜大了，说明答案比50小，然后猜25…用这种方法，每次都可以将数字的范围缩小一
半，对于1~100之间的任何数，最多都只需要7次就能找到答案。
这种每次将搜索范围缩小一半的方法，就是二分法搜索的思想。本文使用 Python 来实现二分法搜索。
一、一、Python 二分法搜索递归实现二分法搜索递归实现
在实现代码前，先分析二分法的前提条件：
1. 上面的例子在1~100中查找一个数字，每次都要判断是大了还是小了，这里隐含了一个条件，即1~100是升序排列的。对于
二分法，数据列表必须是有序的，一般是升序，降序也可以。
2. 跳出1~100的范围，对于任何的数据集合，都可以使用二分法来搜索其中的某个数。
现在来看一下二分法搜索的具体过程。如在 [50, 77, 55, 29, 10, 30, 66, 18, 80, 51] 中搜索 77 。
1. 对列表排序。通常的数据很少是排好序的，要使用二分法，就要先对数据列表进行排序。
2. 取一半位置的数据。对于一个数据集合，数据量可能是奇数，也可能是偶数，但不管奇数偶数，都取2的整除。
所以，这里先找到一半位置的50。
3. 判断中间位置的数字与目标数字的大小，缩小搜索范围，然后重复第2步。
4. 继续重复2和3，直到找到目标数据。
评论10