二分法及Python实现
时间: 2024-05-27 09:06:36 浏览: 15
二分法(Binary Search)是一种常见的查找算法,也叫折半查找。它要求待查找的序列必须有序。每次取中间位置的值与待查关键字进行比较,如果中间位置的值比待查找的值大,则在序列的左半部分继续执行查找;如果中间位置的值比待查找的值小,则在序列的右半部分继续查找,直到查找到为止。
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。
相关问题
python实现二分法求根
二分法求根是一种简单有效的数值计算方法,可以用来寻找函数的零点。以下是Python实现二分法求根的示例代码:
```python
def binary_search_root(f, a, b, tol=1e-6, max_iter=100):
"""
使用二分法求解函数f在区间[a, b]上的根。
:param f: 目标函数
:param a: 区间左端点
:param b: 区间右端点
:param tol: 精度要求
:param max_iter: 最大迭代次数
:return: 根的近似值
"""
fa, fb = f(a), f(b)
if fa * fb > 0:
raise ValueError("函数f在区间[a, b]上没有根。")
for i in range(max_iter):
c = (a + b) / 2
fc = f(c)
if abs(fc) < tol:
return c
if fa * fc < 0:
b, fb = c, fc
else:
a, fa = c, fc
raise ValueError("二分法迭代次数超过了最大值。")
```
其中,f是目标函数,a和b是区间的左右端点,tol是精度要求,max_iter是最大迭代次数。函数首先检查区间上是否存在根,然后使用for循环迭代求解。每次迭代,代码计算区间的中点c,然后根据函数值的符号将区间缩小。如果找到了满足精度要求的根,函数返回根的近似值。如果迭代次数超过了最大值,函数抛出异常。
二分法迭代python代码
二分法(Binary Search)是一种在有序数组中查找特定元素的搜索算法,其基本思想是每次将搜索区间缩小一半。下面是使用 Python 实现的二分查找迭代版本的代码:
```python
def binary_search_iterative(arr, target):
left = 0
right = 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
# 如果没有找到目标,返回 -1 表示未找到
return -1
# 使用方法
arr = [1, 3, 5, 7, 9]
target = 5
result = binary_search_iterative(arr, target)
if result != -1:
print(f"元素 {target} 在数组中的索引为 {result}")
else:
print(f"元素 {target} 未在数组中")
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)