python - 递归二分查找python
问题描述
我一直在尝试递归地编写二进制搜索。当我使用 list[:] 语法执行此操作时,我没有得到预期的结果,出现几个错误或没有得到正确的值。
def binary_search(arr, val):
left = 0
right = len(arr)-1
mid = (left + right)//2
#Go through the array
if (val == arr[mid]):
return mid
#Check right side of arr
if (val > arr[mid]):
return binary_search(arr[mid+1:], val)
#Check left side of arr
return binary_search(arr[:mid], val)
编辑:示例输入和输出
arr1 =[]
for i in range(10):
arr1.append(i)
for i in range(10):
print(binary_search(arr1,i))
我希望得到类似的东西,'0,1,2,3,4,5,6,7,8,9'
但得到'0,1,0,0,4,None ,None,2,0,0'
解决方案
你有两个问题。第一个是错字,你说
if (val > mid):
你应该说
if (val > arr[mid]):
由于您正在比较值而不是索引。
第二个更微妙......当您检查数组的右侧时,在:
return binary_search(arr[mid+1:], val)
您传递给递归调用 ( arr[mid+1:]
) 的子数组已经在数组的中间开始,这意味着该递归调用的结果将返回子数组中元素的索引。因此,您需要添加用于拆分数组的索引增量,以再次获得基于完整数组的索引:
return binary_search(arr[mid+1:], val) + (mid + 1)
这是完整的完整代码:
def binary_search(arr, val):
left = 0
right = len(arr)-1
mid = (left + right)//2
#Go through the array
if (val == arr[mid]):
return mid
#Check right side of arr
if (val > arr[mid]):
return binary_search(arr[mid+1:], val) + (mid + 1)
#Check left side of arr
return binary_search(arr[:mid], val)
推荐阅读
- c++ - 如何在同一帧中替换背景图片和wxBoxSizer?
- arrays - Python itertools.combinations:如何同时获取组合内组合数的索引
- spring-boot - 带有 Springboot 的 Swagger 3:无法推断基本 url
- python - 你如何调试pydoit?
- azure - 微软图形。异常 SubscriptionCountReached 已达到“1000”的限制
- javascript - 在构建应用程序时,Expo/React-Native 将什么捆绑在一起?
- java - 如何使用谷歌助手为我的应用测试 android 切片
- xamarin - Mapsui - 如何提供当前用户的位置和焦点地图?
- c# - Mvvm Wpf MaterialDesign 更新 ViewModel 从另一个 ViewModel(抽屉)
- c# - OverlapCircleAll优化