python二分查找法

lizh

一、概述
　　1、条件
　　不是所有数据类型都可以应用二分查找法,他需要满足以下的条件:
　　是一个有序序列(索引数组),且是已经排好序的序列.
　　2、查找原理
　　在一个有序序列中查找一个指定的数,如果首先和这个序列的中间数相比如果相等就找到返回,如果比这个中间数小,即在序列左边找,如果比中间数大就从右边查找,直到找到或未找到返回.

二、python代码实现
　　知道了条件和原理后,其他任何一门语言都可实现,以下是python代码的简单实现.
　　参考代码
　　

import math　　

　　
L = [1,56,58,60,66,70,7,98,100,111,49999,99999]
　　
count = 0     #定义统计查找次数
　　
#查找是否在列表中
　　
def bin_search(arg,num):
　　global count
　　begin = 0
　　end = len(arg) -1    #最后一个索引
　　mid = math.floor((end - begin)/2)  #获取中间数索引,math.floor用于获取向下取整
　　mid_value = arg[mid]                 #中间数
　　try:
　　if mid_value == num:               #要找的数刚好是中间数
　　count +=1
　　ret = "%d在列表中,共查找了%d" %(num,count)
　　elif mid_value > num:    #说明在左侧
　　count += 1
　　ret = bin_search(arg[:mid],num)  #从原列表的开始到中间索引为新查找的位置
　　else:                      ##说明在右侧
　　count += 1
　　ret = bin_search(arg[mid+1:],num)        #从原列表的中间到最右(后)的位置
　　return ret
　　except:
　　return "%d 不在列表中!" %num
　　

　　查找66是否在列表中 并统计查找次数
　　print(bin_search(L,66))
　　如图:

　　再来查找88时提示没有找到,如图:
　　print(bin_search(L,88))

　　添加以下代码我们看看一个长度为100000的列表中查找L中的各元素各需要多少次
　　

L1 = [ ]　　
for i in range(100000):   #生成100000长度的列表
　　L1.append(i)
　　

　　
for num in L:
　　print(bin_search(L1,num))
　　count = 0
　　

　　运行结果如下:

　　请注意:在一个长度为100000的序列中找49999这个数,一次就找到了,只因为它是中间数.

总结:
　　通过二分查找法去查找一个数是否在列表中,要查找的数是中间数时,只要一次就能找到,最差的情况就是n/2 =0时,n为序列长度  但最后等于0时要么找到要么没有找到.不管怎么样比冒泡排序效率要高的多.不需要一个一个的元素比对.