python二分查找算法的递归实现方法_Python

python二分查找算法的递归实现方法

2020-08-22 10:16xuebuyuan Python

这篇文章主要介绍了python二分查找算法的递归实现方法,结合实例形式分析了Python二分查找算法的相关实现技巧,需要的朋友可以参考下

本文实例讲述了python二分查找算法的递归实现方法。分享给大家供大家参考，具体如下：

这里先提供一段二分查找的代码：

				?

									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))

近来喜欢递归的简单明了，所以修改成递归的方法：

				?

									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) #找前半部分