Python实现二分法查找
1、打开Python开发工具IDLE,新建‘search.py’编写代码如下：
list1 = [1,6,3,7,2,0]
list1.sort()
print (list1)
2、F5运行程序，list1被正确排序，写这个的目的是说明二分法查找必须前提是一个有序的列表，如果一开始无序首先要排序，当数据量大的时候，快速排序是一个很好的选择，再进行二分法查找。
Shell中打印内容如下：
[0, 1, 2, 3, 6, 7]
3、接下来定义我们的二分法查找函数，也是用递归的思想，递归就一定有结束条件。代码如下：
def search(li,item):
mid = len(li)//2
if item == li[mid]:
return True
elif item > li[mid]:
return search(li[mid+1:],item)
else:
return search(li[:mid],item)
4、递归结束条件可以有两种写法：
第一种
if len(li)==1: #li长度等于1，只比较这个列表元素与要查找到值
return li[0]==item
完整代码:
def search(li,item):
if len(li)==1:
return li[0]==item
mid = len(li)//2
if item == li[mid]:
return True
elif item > li[mid]:
return search(li[mid+1:],item)
else:
return search(li[:mid],item)
5、第二种
if len(li)==0: #li长度等于0，全部查找结束还是没有这个值
return False
完整代码：
def search(li,item):
if len(li)==0:
return False
mid = len(li)//2
if item == li[mid]:
return True
elif item > li[mid]:
return search(li[mid+1:],item)
else:
return search(li[:mid],item)
6、为程序添加main方法，完整代码如下：
def search(li,item):
if len(li)==0:
return False
mid = len(li)//2
if item == li[mid]:
return True
elif item > li[mid]:
return search(li[mid+1:],item)
else:
return search(li[:mid],item)
if __name__ == '__main__':
list1 = [8,7,2,9]
list1.sort()
print (search(list1,1))
print (search(list1,2))
7、F5运行程序，正确打印出二分法查找结果
False
True
