Python二分法源码
需积分: 0 141 浏览量
2023-07-12
13:29:00
上传
评论
收藏 13KB DOCX 举报
Python 二分法
二分法（Binary Search）是一种高效的搜索算法，常用于有序数组中的查找操作。它通过将
查找范围逐渐缩小一半来定位目标元素。
下面是一个使用 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
elif guess < target:
low = mid + 1
else:
high = mid - 1
return -1 # 目标元素不在数组中
# 示例用法
array = [1, 3, 5, 7, 9]
target = 5
result = binary_search(array, target)
if result != -1:
print("目标元素在索引", result, "处")
else:
print("目标元素不在数组中")
```
这个示例中，`binary_search` 函数接受一个有序数组 `arr` 和一个目标元素 `target`，并返
回目标元素在数组中的索引。如果目标元素不存在于数组中，函数将返回 `-1`。
在二分法中，我们首先将查找范围定义为数组的首尾元素。然后，我们计算中间元素的索引
`mid`，并与目标元素进行比较。如果中间元素等于目标元素，我们找到了目标元素并返回
其索引。如果中间元素小于目标元素，我们将查找范围缩小为右半部分（即 `mid` 右侧）。
如果中间元素大于目标元素，我们将查找范围缩小为左半部分（即 `mid` 左侧）。通过反复
缩小查找范围，最终我们可以找到目标元素或确定目标元素不存在于数组中。
资源评论
Bunnyfox
- 粉丝: 0
- 资源: 7
