python 二分查找 怎么写
时间: 2023-08-27 10:11:11 浏览: 75
### 回答1:
下面是一个简单的Python二分查找算法:
def binary_search(list, item):
low = 0
high = len(list) - 1 while low <= high:
mid = (low + high) // 2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
### 回答2:
二分查找又称折半查找,是一种效率较高的查找算法。以下是Python的二分查找算法的实现步骤:
1. 首先,确定要查找的有序列表,将其赋值给变量arr。
2. 定义要查找的目标元素target。
3. 设定起始下标low为0,终止下标high为列表长度减1。
4. 使用while循环,判断low是否小于等于high。如果条件满足,继续执行循环,反之退出循环。
5. 计算中间元素的下标mid = (low + high) // 2。
6. 判断中间元素arr[mid]与目标元素target的关系:
- 若arr[mid]等于target,表示已找到目标元素,返回mid。
- 若arr[mid]大于target,表示目标元素在左侧,将high更新为mid-1。
- 若arr[mid]小于target,表示目标元素在右侧,将low更新为mid+1。
7. 如果循环结束,仍未找到目标元素,返回-1表示查找失败。
下面是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:
high = mid - 1
else:
low = mid + 1
return -1
# 测试
arr = [1, 3, 5, 7, 9]
target = 7
result = binary_search(arr, target)
if result != -1:
print(f"目标元素在列表中的索引为:{result}")
else:
print("未找到目标元素")
```
以上代码在已知有序列表中进行二分查找,并返回目标元素在列表中的索引。若未找到目标元素,则输出未找到的提示信息。
### 回答3:
二分查找是一种高效的查找算法,适用于已排序的数据集合。下面是用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
return -1
```
函数binary_search接受两个参数,一个是已排序的数组arr,另一个是目标值target。算法使用两个指针low和high分别指向数组的第一个和最后一个元素。然后,使用一个循环来缩小搜索范围,直到找到目标值或者搜索范围为空。
在每一次循环中,算法计算中间元素的索引mid,并将其与目标值进行比较。如果mid对应的元素等于target,则返回mid表示找到目标值的索引。
如果mid对应的元素小于target,则说明目标值应该在[mid+1, high]范围内,因此将low指针移到mid右侧。
如果mid对应的元素大于target,则说明目标值应该在[low, mid-1]范围内,因此将high指针移到mid左侧。
如果循环结束时仍未找到目标值,则返回-1表示未找到。
以上就是用Python实现二分查找算法的方法。这个算法的时间复杂度为O(log n),其中n是数组的长度。由于每次循环将搜索范围缩小一半,因此效率非常高。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)