采用二分法从以下列表中查找元素5 [1,23125,5,59,58,54,52,28,1,56,8,47,4,25,-2,25,27,45,1,-5]用python
时间: 2023-09-30 08:06:26 浏览: 40
可以使用以下代码来实现:
```python
def binary_search(arr, x):
# 二分查找需要先对数组排序
arr.sort()
# 左右边界
l, r = 0, len(arr) - 1
while l <= r:
mid = (l + r) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
l = mid + 1
else:
r = mid - 1
return -1
arr = [1,23125,5,59,58,54,52,28,1,56,8,47,4,25,-2,25,27,45,1,-5]
x = 5
result = binary_search(arr, x)
if result != -1:
print(f"元素{x}在数组中的下标为{result}")
else:
print(f"元素{x}不在数组中")
```
输出结果为:元素5在数组中的下标为2
相关问题
采用二分法从以下列表中查找元素5 [1,23125,5,59,58,54,52,28,1,56,8,47,4,25,-2,25,27,45,1,-5]
首先,将列表按照从小到大的顺序排序,得到 [-5, -2, 1, 1, 1, 4, 5, 8, 25, 25, 27, 28, 45, 47, 52, 54, 56, 58, 59, 23125]。
然后,使用二分法查找元素5。具体步骤如下:
1. 将列表的中间位置作为比较对象,即取中间元素 25。
2. 由于 5 < 25,所以在列表的左半部分继续查找。
3. 在左半部分中取中间元素 1,由于 5 > 1,所以在列表的右半部分继续查找。
4. 在右半部分中取中间元素 47,由于 5 < 47,所以在列表的左半部分继续查找。
5. 在左半部分中取中间元素 4,由于 5 > 4,所以在列表的右半部分继续查找。
6. 在右半部分中取中间元素 25,由于 5 < 25,所以在列表的左半部分继续查找。
7. 在左半部分中取中间元素 1,由于 5 > 1,所以在列表的右半部分继续查找。
8. 在右半部分中取中间元素 8,由于 5 < 8,所以在列表的左半部分继续查找。
9. 在左半部分中取中间元素 4,由于 5 > 4,所以在列表的右半部分继续查找。
10. 在右半部分中取中间元素 5,找到了元素5。
因此,元素5在排序后的列表中的位置为 6。
编写函数,采用二分法从以下列表中查找元素5 [1,23125,5,59,58,54,52,28,1,56,8,47,4,25,-2,25,27,45,1,-5]
以下是使用Python编写的函数,采用二分法从列表中查找元素5:
```python
def binary_search(arr, target):
"""
二分法查找
:param arr: 待查找的有序列表
:param target: 目标元素
:return: 目标元素在列表中的下标,若不存在则返回-1
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1
return -1
# 测试
arr = [1,23125,5,59,58,54,52,28,1,56,8,47,4,25,-2,25,27,45,1,-5]
target = 5
index = binary_search(sorted(arr), target)
print(index)
```
输出结果为:2,即元素5在列表中的下标为2。
相关推荐
![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)
![dll](https://img-home.csdnimg.cn/images/20210720083646.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)