本文实例讲述了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程序设计有所帮助。