python二分查找算法怎么应用

56次阅读
没有评论

共计 803 个字符,预计需要花费 3 分钟才能阅读完成。

二分查找算法是一种高效的查找算法,可以用于在有序数组中查找特定元素。其基本思想是将查找区间不断二分,然后根据中间元素与目标元素的大小关系,缩小查找区间,直到找到目标元素或者确定目标元素不存在。
以下是一个简单的示例代码,演示了二分查找算法的应用:

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 = [1, 3, 5, 7, 9, 11, 13]
target = 5
result = binary_search(arr, target)
if result != -1:
print(" 目标元素在数组中的索引为 ", result)
else:
print(" 目标元素不在数组中 ")

上述示例中,binary_search函数接受一个有序数组 arr 和一个目标元素 target 作为参数,返回目标元素在数组中的索引。如果目标元素不存在于数组中,则返回 -1。
在示例中,算法首先定义了查找区间的左右边界 leftright,初始时分别为数组的第一个和最后一个元素的索引。然后进入一个循环,每次循环将查找区间二分为两个子区间,然后根据中间元素与目标元素的大小关系,更新左右边界。如果中间元素等于目标元素,则找到目标元素,返回其索引。如果中间元素小于目标元素,则目标元素应该在右子区间中,更新左边界为中间元素的下一个位置。如果中间元素大于目标元素,则目标元素应该在左子区间中,更新右边界为中间元素的上一个位置。循环结束条件是左边界大于右边界。
通过二分查找算法,可以快速地在有序数组中查找目标元素,时间复杂度为 O(log n)。

丸趣 TV 网 – 提供最优质的资源集合!

正文完
 
丸趣
版权声明:本站原创文章,由 丸趣 2023-12-21发表,共计803字。
转载说明:除特殊说明外本站除技术相关以外文章皆由网络搜集发布,转载请注明出处。
评论(没有评论)