Python实现二分查找的函数
在计算机科学中，二分查找是一种高效的查找算法，它的基本思想是将目标值与序列的中间元素进行比较，如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在序列的左半部分继续查找；如果目标值大于中间元素，则在序列的右半部分继续查找，这个过程可以递归地进行，直到找到目标值或者序列为空。
下面是一个使用Python实现的二分查找的函数：
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return None
这个函数接受两个参数：一个排序好的列表`arr`和一个目标值`target`，它首先初始化两个指针`low`和`high`，分别指向列表的开始和结束，然后进入一个循环，只要`low`不大于`high`，就继续循环，在每次循环中，它首先计算中间元素的索引`mid`，然后获取该索引处的元素`guess`，如果`guess`等于`target`，则返回`mid`；如果`guess`大于`target`，则将`high`设置为`mid - 1`；否则，将`low`设置为`mid + 1`，如果在循环结束后还没有找到`target`，则返回`None`。
这个函数的时间复杂度是O(log n)，其中n是列表的长度，这是因为每次循环都会将搜索范围减半，这使得二分查找在处理大型数据集时非常高效。
原创文章，作者：K-seo，如若转载，请注明出处：https://www.kdun.cn/ask/9468.html
微信扫一扫 