c++与python实现二分查找的原理及实现
目录
- 1、时间复杂度与优缺点
- 2、python实现
- 3、C++实现
作为查找算法家族中的一员,二分查找正是利用数据按次序存储这一优点,极大的提升了查找目标值所在位置的速度。
二分查找的核心思想是:首先将数组中间值和目标值进行比较,如果相等则返回;如果不相等,则选择中间值左边的一半或者右边的一半进行比较;不断重复直到检索完毕。首先来看下面这个gif,其中蓝色圈表示左位置,粉色圈表示右位置,绿色圈表示中间位置:
![c++与python实现二分查找的原理及实现](https://img.it610.com/image/info11/95d41401ce444e9caf8155278e933ecc.gif)
文章图片
【c++与python实现二分查找的原理及实现】首先定义的是左边界(蓝色圈)和右边界(粉色圈),进而根据左边界和右边界计算出中间位置(绿色圈);然后,比较中间位置的值和目标值的大小,比较结果包含3种情况
- 如果相等则表示查找成功,返回中间位置;
- 如果中间位置的值小于目标值,则说明目标值在中间位置到右边界这一半;
- 如果中间位置的值大于目标值,则说明目标值在左边界到中间位置这一半;
1、时间复杂度与优缺点 既然每次搜索后区间长度都减半,假设数据个数(即区间长度)为n,那么算法每次迭代得到的区间长度依次为n/2,n/4,n/8等等,其通项如下,k表示循环次数:
![c++与python实现二分查找的原理及实现](https://img.it610.com/image/info11/851b4d0afd404be786663eecebe71cf9.png)
文章图片
最坏的情况,就是搜索到区间长度为1,即最后只剩1个元素:
![c++与python实现二分查找的原理及实现](https://img.it610.com/image/info11/c73fd3566f50458faf0844e7bef383db.png)
文章图片
所以,可以求得最坏情况下需要运行的次数为:
![c++与python实现二分查找的原理及实现](https://img.it610.com/image/info11/6b7c28d2a8ab4882b284e3c98a3d0fb3.png)
文章图片
因此二分查找复杂度为O(logn),相比于顺序查找其速度获得了极大的提高(优点)。但是,必须注意二分查找需要保证数据是有序的,这就要求数据必须预先进行排序(缺点)。
2、python实现
def binary_search(ordered_list, target_value):"""Args:ordered_list: data with ordertarget_value: value that want be searched"""left = 0right = len(ordered_list)-1# 终止条件while left <= right:# 中间位置计算mid = int((left+right)/2)if ordered_list[mid] == target_value:return "index is {}, target value is {}".format(mid, ordered_list[mid])# 此时目标值在中间值右边,更新左位置elif ordered_list[mid] < target_value:left = mid + 1# 此时目标值在中间值左边,更新右位置elif ordered_list[mid] > target_value:right = mid - 1# 搜索结束没有找到return "Not find"
3、C++实现
int binarySearch(int *orderedData, int dataLength, int targetValue) {int left = 0; int right = dataLength - 1; int mid; // 终止条件while (left<=right){// 中间位置计算mid = (left + right) / 2; if (*(orderedData + mid) == targetValue) {return mid; }// 目标值在中间值右边,更新左位置else if (*(orderedData + mid) < targetValue){left = mid + 1; }// 目标值在中间值左边,更新右位置else{right = mid - 1; }}// 搜索不到,返回-1return -1; }
到此这篇关于c++与python实现二分查找的原理及实现的文章就介绍到这了,更多相关c++与python实现二分查找内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- Python绘画好看的星空图
- Python|Python eval()函数和ast.literal_eval()的区别你知道吗
- Python+folium绘制精美地图的示例详解
- Python中plt.plot()、plt.scatter()和plt.legend函数的用法示例
- python中parser.add_argument()用法实例(命令行选项、参数和子命令解析器)
- Python|Python 分形算法代码详解
- C/C++|std::is_trivially_destructible
- linux系统编程|详解僵尸进程与孤儿进程
- Apache Impala架构解析及与Hive、SparkSQL的性能比较
- 高级前端工程之路|《代码规范》如何写出干净的代码(二)函数与方法