本文实例讲述了python二分查找算法的递归实现方法。分享给大家供大家参考，具体如下：
这里先提供一段二分查找的代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def binarySearch(alist, item):
first = 0
last =
len(alist)-1
found = False
while first<=last
and not found:
midpoint = (first + last)//2
if alist[midpoint] == item:
found = True
else:
if item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return found
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binarySearch(testlist, 3))
print(binarySearch(testlist, 13))
|
近来喜欢递归的简单明了，所以修改成递归的方法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def binSearch(lst, item):
mid = len(lst) //2
found = False
if lst[mid] ==
item:
found = True
return found
if mid == 0:
#mid等于0就是找到最后一个元素了。
found = False
return found
else:
if item > lst[mid]: #找后半部分
#print(lst[mid:])
return
binSearch(lst[mid:], item)
else:
return
binSearch(lst[:mid], item) #找前半部分
|
测试通过。
希望本文所述对大家Python程序设计有所帮助。