Question

各位大神好，本菜鸟初学python，请问如何用递归来实现二分法算法呢？我自己编了个，但是不明白哪里错了

def erfenfa(l,num):
low=0
high=len(l)-1
mid=int(len(l)/2)
if len(l)>1:

if num>l[mid]:
l1=l[mid:]
erfenfa(l1,num)

elif num<l[mid]:
l2=l[:mid]
erfenfa(l2,num)

elif num==l[mid]:
print('exist',mid)

else: print('not exist')

return None

l=[1,2,3,10,20,30,50,60,100]
erfenfa(l,20)

Answer 1

因为你改变了列表l的大小,所以它输出的不是在原列表l的序号,而是在子列表的序号

因此不改变列表l,而只需要改变搜索范围,就能找到数的正确位置了.

完整的程序如下(改动的地方见注释)

def erfenfa(l,num,low,high): #这里增加两个参数

 #low=0 #这里去掉这句

 #high=len(l)-1 #这里去掉这句

 mid=int((low+high)/2)#这里把len(l)/2改成(low+high)/2

 if low<mid: #这里把len(l)>1改成low<mid

  if num>l[mid]:

   #l1=l[mid:] #这里去掉这句

   erfenfa(l,num,mid,high) #这里增加两个参数

  elif num<l[mid]:

   #l2=l[:mid] #这里去掉这句

   erfenfa(l,num,low,mid) #这里增加两个参数

  elif num==l[mid]:

   print('exist',mid)

 else:

   print('not exist')

 #return None #这里去掉这句

l=[1,2,3,10,20,30,50,60,100]

erfenfa(l,50,0,len(l)-1)

源代码(注意源代码的缩进)

Answer 2

按照你的代码，可以正常运行啊，估计你是缩进的问题，我把缩进好的拍给你

Answer 3

def binSearch(numList, left, right, num):
	if left > right:
		return -1
	mid = (left + right) / 2
	if num == numList[mid]:
		return mid
	elif num < numList[mid]:
		return binSearch(numList, left, mid-1, num)
	else:
		return binSearch(numList, mid+1, right, num)

nums = [1,2,3,10,20,30,50,60,100]
print(binSearch(nums, 0, len(nums)-1, 20))
print(binSearch(nums, 0, len(nums)-1, 50))
print(binSearch(nums, 0, len(nums)-1, 60))
print(binSearch(nums, 0, len(nums)-1, 2))
print(binSearch(nums, 0, len(nums)-1, -20))
print(binSearch(nums, 0, len(nums)-1, 120))
print(binSearch(nums, 0, len(nums)-1, 25))

4
6
7
1
-1
-1
-1