编写程序,输入一个数字n,用二分查找法,查找n是否存在于列表[1,3,5,11,21,25,33,72,97,99]中。
时间: 2023-10-22 16:09:52 浏览: 37
以下是Python代码实现:
```python
def binary_search(arr, x):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == x:
return True
elif arr[mid] < x:
low = mid + 1
else:
high = mid - 1
return False
n = int(input("请输入一个数字:"))
arr = [1, 3, 5, 11, 21, 25, 33, 72, 97, 99]
if binary_search(arr, n):
print("数字存在于列表中")
else:
print("数字不存在于列表中")
```
运行程序后,输入一个数字,程序会使用二分查找法查找该数字是否存在于列表中,并输出查找结果。
相关问题
python编写程序,输入一个数字n,用二分查找法,查找n是否存在于列表[1,3,5,11,21,25,33,72,97,99]中。
下面是使用二分查找法在Python中查找数字n是否存在于给定的列表中的示例代码:
```python
def binary_search(arr, n):
"""
二分查找函数
:param arr: 有序列表
:param n: 待查找的元素
:return: 元素在列表中的位置,如果不存在则返回-1
"""
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == n:
return mid
elif arr[mid] < n:
low = mid + 1
else:
high = mid - 1
return -1
# 测试
arr = [1, 3, 5, 11, 21, 25, 33, 72, 97, 99]
n = int(input("请输入一个数字:"))
result = binary_search(arr, n)
if result == -1:
print("数字%d不存在于列表中" % n)
else:
print("数字%d存在于列表中,位置为%d" % (n, result))
```
运行示例:
```
请输入一个数字:11
数字11存在于列表中,位置为3
```
```
请输入一个数字:35
数字35不存在于列表中
```
编写程序,实现用二分查找法在列表中查找指定的元素。
这里是一个Python的二分查找示例程序:
```python
def binary_search(arr, target):
"""
在有序列表 arr 中查找目标元素 target 的下标,
如果找到了则返回其下标,否则返回 -1。
"""
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。它用 left 和 right 两个变量表示当前搜索范围的左右边界,初始时左边界为 0,右边界为列表长度减 1。在每次循环中,我们计算中间位置 mid,并比较 arr[mid] 和 target 的大小关系。如果 arr[mid] 等于 target,则直接返回 mid;如果 arr[mid] 小于 target,则说明目标元素在右半部分,更新左边界 left 为 mid + 1;如果 arr[mid] 大于 target,则说明目标元素在左半部分,更新右边界 right 为 mid - 1。如果循环结束了还没有找到目标元素,则返回 -1 表示未找到。
下面是一个使用示例:
```python
arr = [1, 3, 4, 7, 8, 10]
target = 4
idx = binary_search(arr, target)
if idx == -1:
print(f"{target} not found")
else:
print(f"{target} found at index {idx}")
```
这个程序会输出:
```
4 found at index 2
```