编写函数fun(ls,target,low,high), 递归实现二分法查找。 对有序列表ls=[7,9,12,34,57,89,123,221,345,456]进行二分法查找,根据查找目标数据target。若查找成功,返回True;否则返回False。 low表示查找区域起始位置;high表示查找区域终止位置
时间: 2023-06-09 07:02:39 浏览: 261
好的,让我来回答你的问题。下面是对应的Python代码:
def fun(ls, target, low, high):
if low > high: # 如果查找区域不存在,返回False
return False
mid = (low + high) // 2 # 计算区域中间位置的下标
if ls[mid] == target: # 如果目标值等于中间位置的值,返回True
return True
elif ls[mid] > target: # 如果目标值在查找区域的左侧,递归查找左侧区域
return fun(ls, target, low, mid-1)
else: # 如果目标值在查找区域的右侧,递归查找右侧区域
return fun(ls, target, mid+1, high)
# 测试代码
ls = [7, 9, 12, 34, 57, 89, 123, 221, 345, 456]
target = 89
print(fun(ls, target, 0, len(ls)-1)) # 输出 True
对于上述代码,首先定义了一个名为fun
的函数,其中ls
表示要查找的有序列表,target
表示要查找的目标数据,low
表示查找区域的起始位置,high
表示查找区域的终止位置。函数的实现方式是递归的二分法查找。
如果查找区域起始位置low
大于终止位置high
,说明查找区域不存在目标数据,返回False
。否则,根据区域中间位置的下标mid
,判断目标数据在左侧还是右侧,然后递归地对左侧或右侧区域进行查找。
最后,利用输入的有序列表ls
和目标数据target
进行测试,输出查找结果即可。
相关推荐
















