Python实现二分法
时间: 2024-08-11 12:01:52 浏览: 55
二分查找,也称为折半查找,是一种在有序数组中查找特定元素的搜索算法。它的工作原理是每次将待查找区间缩小一半,直到找到目标值或确定区间为空。以下是Python中实现二分查找的基本步骤:
```python
def binary_search(arr, target):
low = 0 # 区间开始下标
high = len(arr) - 1 # 区间结束上标
while low <= high:
mid = (low + high) // 2 # 计算中间位置
if arr[mid] == target: # 如果中间值就是目标,返回索引
return mid
elif arr[mid] < target: # 如果中间值小于目标,调整区间的下界到中间偏右一位
low = mid + 1
else: # 如果中间值大于目标,调整区间的上界到中间偏左一位
high = mid - 1
# 如果遍历结束后仍未找到目标,返回-1表示未找到
return -1
# 使用示例
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search(arr, target)
if result != -1:
print(f"找到了,索引为 {result}")
else:
print("没找到")
```
相关问题
python实现二分法求根
二分法求根是一种常见的数值计算方法,可以用来求解函数的零点。以下是Python实现二分法求根的示例代码:
```python
def bisection(func, a, b, tol=1e-6, maxiter=100):
"""
二分法求根
:param func: 目标函数,输入一个实数,返回一个实数
:param a: 区间左端点
:param b: 区间右端点
:param tol: 误差容限,默认为 1e-6
:param maxiter: 最大迭代次数,默认为 100
:return: 方程的根
"""
fa, fb = func(a), func(b)
if fa * fb > 0:
raise ValueError("区间端点函数值符号相同,无法使用二分法")
for i in range(maxiter):
c = (a + b) / 2
fc = func(c)
if abs(fc) < tol:
return c
if fa * fc < 0:
b, fb = c, fc
else:
a, fa = c, fc
raise RuntimeError("二分法未收敛")
```
该函数的输入是目标函数 `func`、区间左端点 `a` 和右端点 `b`,以及误差容限 `tol` 和最大迭代次数 `maxiter`。函数的输出是方程的根。
在函数内部,首先计算区间端点的函数值 `fa` 和 `fb`,如果它们的符号相同,则抛出异常。然后进行迭代,每次将区间中点 `c` 计算为 `(a+b)/2`,并计算函数值 `fc`。如果 `fc` 的绝对值小于误差容限 `tol`,则认为已经找到了根,返回 `c`。如果 `fa` 和 `fc` 的符号不同,则说明根位于区间的左半部分,将右端点 `b` 更新为 `c`,并更新 `fb` 为 `fc`。否则,根位于区间的右半部分,将左端点 `a` 更新为 `c`,并更新 `fa` 为 `fc`。如果迭代次数达到了最大值 `maxiter`,则抛出运行时异常。
给我一个python实现二分法
好的,这里是Python实现的二分法:
```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。
阅读全文