二分查找(Binary Search)是一种在有序数组中查找特定元素的搜索算法,它的工作原理是每次比较数组中间元素与目标值,如果中间元素正好等于目标值,则查找成功;如果目标值小于中间元素,则在数组的左半部分继续查找;如果目标值大于中间元素,则在数组的右半部分继续查找,通过不断缩小查找范围,直到找到目标值或者查找范围为空。
下面是一个Python实现的二分查找函数:
def binary_search(arr, target): left, right = 0, len(arr) 1 while left <= right: mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: left = mid + 1 else: right = mid 1 return 1
这个函数接受两个参数:一个有序数组arr
和一个目标值target
,函数返回目标值在数组中的索引,如果目标值不存在于数组中,则返回1。
现在我们来详细解释一下这个函数的实现过程:
1、初始化两个指针left
和right
,分别指向数组的第一个元素和最后一个元素。
2、使用while
循环,当left
小于等于right
时,执行循环体,这是因为如果left
大于right
,说明查找范围已经为空,目标值不存在于数组中。
3、计算中间元素的索引mid
,这里使用整数除法//
,以避免出现小数。
4、比较中间元素arr[mid]
与目标值target
:
如果arr[mid]
等于target
,说明找到了目标值,返回其索引mid
。
如果arr[mid]
小于target
,说明目标值位于数组的右半部分,将left
更新为mid + 1
。
如果arr[mid]
大于target
,说明目标值位于数组的左半部分,将right
更新为mid 1
。
5、如果循环结束后仍未找到目标值,说明目标值不存在于数组中,返回1。
需要注意的是,二分查找算法要求输入的数组是有序的,在使用二分查找之前,请确保数组已经按照升序或降序排列。
原创文章,作者:酷盾叔,如若转载,请注明出处:https://www.kdun.com/ask/345814.html
本网站发布或转载的文章及图片均来自网络,其原创性以及文中表达的观点和判断不代表本网站。如有问题,请联系客服处理。
发表回复