python的二分查找实现

基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右 半部继续搜索x。

优点：比较次数少，查找速度快，平均性能好

缺点：待查表为有序表，且插入删除困难

python代码：

def binarySearch(lists,select):
    i=0
    j=len(lists)-1
    for k in range(j/2+1):
        if i>j:
            return -1
        zj = (i+j)/2
        if lists[zj] == select:
            return zj
        elif lists[zj] > select:
            j = zj - 1
        else:
            i =zj + 1

if __name__ == "__main__":
    arr = [1,4,6,8,9,11]
    print binarySearch(arr,6)