Python实现经典查找算法

yinian

　　1.二分查找:
　　Note:二分查找列表必须是有序的
　　原理：选定列表起点和终点索引，计算中间索引，如果要查找的值恰好等于中间索引对应的值则直接返回中间索引，如果要查找的值小于中间索引值，则从中间索引为界的前半部分查找（sindex~mid-1），反之从后半部分查找(mid+1~eindex)，mid+1,mid-1的原因mid已经对比过了，从前一个或后一个开始对比，加while条件直到遍历所有结果，没找到返回-1.
　　def binary_search(find, _list):  # 二分查找
　　sindex = 0
　　eindex = len(_list)
　　while sindex < eindex:
　　mid = (sindex + eindex)/2
　　if _list[mid] == find:
　　return mid
　　elif _list[mid] > find:
　　eindex = mid - 1
　　else:
　　sindex = mid + 1
　　return -1
　　2.斐波数列：
　　不够pythonic示范，多次循环对列表切片取值，append开销较大
　　def fib(number):
　　_list = [0,1]
　　for i in range(number-1):
　　_list.append(_list[-2]+_list[-1])
　　return _list[1:]
　　更好示范：
　　def fib(number):
　　a, b = 0, 1
　　_list = []
　　for i in range(number):
　　a, b = a+b, a
　　_list.append(a)
　　return _list