二分查找算法之python实现

二分查找也叫折半查找，通过不断比较目标元素与一个有序序列（注意是有序序列）中间元素的值，达到每次查找都能排除一半元素的一种算法。

python实现如下：

#!/usr/bin/python
# -*- coding: utf-8 -*-

import random

unsortedList=[]

# generate an unsorted list
def generateUnsortedList(num):
	for i in range(0,num):
		unsortedList.append(random.randint(0,100))
	print unsortedList

def binarySearch(target,sortedList):
	list_length=len(sortedList)
	start,end=0,list_length-1
	if list_length==0:
		print 'empty list'
		return -1
	while start<end:
		middle=(start+end)/2
		if target==sortedList[middle]:
			print 'find index:',middle
			return middle
		elif target<sortedList[middle]:
			end=middle-1
		else:
			start=middle+1
	print 'not find'
	return -1


generateUnsortedList(20)
sortedList=sorted(unsortedList)
print sortedList

binarySearch(14,sortedList)