《Python二分查找法》主讲人:刘杨河北交通职业技术学院
1目录Python二分查找法2应用示例在jupyternotebook中运行二分查找原理3
1二分查找原理
二分查找原理二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分查找原理在有序数列中查找数字4。第一步第二步第三步最终
2应用示例
应用示例#返回x在arr中的索引下标,如果不存在返回-1defbinarySearch(arr,l,r,x): ifr=l: #基本判断 mid=int(l+(r-l)/2) ifarr[mid]==x: #元素正好在中间位置 returnmid elifarr[mid]x: #元素小于中间位置的元素,只需要再比较左边的元素 returnbinarySearch(arr,l,mid-1,x) else: #元素大于中间位置的元素,只需要再比较右边的元素 returnbinarySearch(arr,mid+1,r,x) else: return-1 #不存在
应用示例arr=[2,3,4,10,40] #测试数组x=10#函数调用result=binarySearch(arr,0,len(arr)-1,x)ifresult!=-1:print(“元素在数组中的索引下标为:%d%result)else:print(元素不在数组中)执行以上代码输出结果为:元素在数组中的索引下标为:3
3在jupyternotebook中运行
在jupyternotebook中运行
总结通过以上学习需注意的主要问题:理解python语言的递归调用的方法,掌握二分法的使用,熟悉在jupyternotebook中运行程序,查看结果。
谢谢观看