def binarySearch(s,v): begin,end = 0, len(s)-1 isfound = False while begin <= end: mid = # 取得中位元素在队列中的序号 if s == v: # 将中位元素与目标比较 isfound = True print("Found:%d" % mid) break elif v > s : # 如果目标>中位元素 # 更新搜索的起始位置 else: end = mid - 1 if isfound == False: print("Not found") a = [1,3, 12, 45, 66, 89, 123, 154, 768, 9921] binarySearch(a,89) 运行结果: Found: 5
时间: 2024-02-10 12:35:24 浏览: 24
这是一个二分查找算法的 Python 实现,它接收两个参数:一个有序的列表 s 和一个要查找的值 v。它首先将搜索的起始位置 begin 和结束位置 end 初始化为列表的起始位置和结束位置。在 while 循环中,它计算中位元素的位置 mid,并将其与目标值 v 进行比较。如果它们相等,它将打印出 mid 的值,并将 isfound 标志设为 True。如果 v 大于中位元素 s[mid],则将 begin 更新为 mid + 1;否则将 end 更新为 mid - 1。如果在循环结束时 isfound 仍然为 False,则打印出 "Not found"。在这个例子中,给定列表 a 中的值为 [1,3, 12, 45, 66, 89, 123, 154, 768, 9921],要查找的值为 89,因此该函数打印出 "Found: 5",表示值 89 在列表的第 5 个位置。
相关问题
下述程序中的binarySearch()函数通过折半查找从列表a中查找并打印元素89的下标。请将其补充完整。 def binarySearch(s,v): begin,end = 0, len(s)-1 isfound = False while begin <= end: mid = # 取得中位元素在队列中的序号 if s == v: # 将中位元素与目标比较
下面是将程序补充完整的代码:
```python
def binarySearch(s, v):
begin, end = 0, len(s) - 1
isfound = False
while begin <= end:
mid = (begin + end) // 2 # 取得中位元素在队列中的序号
if s[mid] == v: # 将中位元素与目标比较
isfound = True
print("Found: %d" % mid)
break
elif v > s[mid]:
begin = mid + 1 # 如果目标>中位元素,更新搜索的起始位置
else:
end = mid - 1 # 如果目标<中位元素,更新搜索的结束位置
if not isfound:
print("Not found")
```
这个函数使用了二分查找算法。它接收两个参数:一个有序的列表 s 和一个要查找的值 v。它首先将搜索的起始位置 begin 和结束位置 end 初始化为列表的起始位置和结束位置。在 while 循环中,它计算中位元素的位置 mid,并将其与目标值 v 进行比较。如果它们相等,它将打印出 mid 的值,并将 isfound 标志设为 True。如果 v 大于中位元素 s[mid],则将 begin 更新为 mid + 1;否则将 end 更新为 mid - 1。如果在循环结束时 isfound 仍然为 False,则打印出 "Not found"。在这个例子中,给定列表 a 中的值为 [1, 3, 12, 45, 66, 89, 123, 154, 768, 9921],要查找的值为 89,因此该函数打印出 "Found: 5",表示值 89 在列表的第 5 个位置。
完善Binary_search(lt)函数,实现二分查找功能。 def Binary_search(lt): low=0 high=len(lt)-1 flag=False lt=eval(input()) x=eval(input()) if Binary_search(lt)==True: print('找到该数') else: print('未找到该数')
可以参考下面的代码来完善Binary_search(lt)函数:
```
def Binary_search(lt, x):
low = 0
high = len(lt) - 1
while low <= high:
mid = (low + high) // 2
if lt[mid] == x:
return True
elif lt[mid] < x:
low = mid + 1
else:
high = mid - 1
return False
lt = eval(input())
x = eval(input())
if Binary_search(lt, x):
print('找到该数')
else:
print('未找到该数')
```
在这个函数中,我们传入两个参数:要搜索的列表lt和要搜索的值x。我们通过low和high两个变量来记录搜索范围的下界和上界,并且使用一个while循环来不断缩小搜索范围。在每次循环中,我们计算出中间位置mid,并且将mid处的值与x进行比较。
如果mid处的值等于x,那么我们就找到了这个值,返回True。如果mid处的值小于x,那么我们就将搜索范围缩小到右半边,也就是将low更新为mid+1。如果mid处的值大于x,那么我们就将搜索范围缩小到左半边,也就是将high更新为mid-1。如果循环结束后还没有找到x,那么就返回False。
最后,我们可以通过调用Binary_search函数来查找列表中是否存在x,并且根据返回值来输出相应的提示信息。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)