0基础教程习题16—二分查找法

1、题目要求

 

实现二分查找法，函数定义如下

def binary_search(lst,targt)

---

2、程序分析

 

二分查找法，只能用于有序的列表，想要查找一个元素在列表中的位置，则先把列表中间的元素拿出来和这个待查找的元素进行比较，比较的结果只有三种

1. 待查找元素和中间元素相等，返回中间位置
2. 待查找元素比中间元素大，中间位置之前的元素就不需要再去查找比对了
3. 待查找元素比中间元素小，中间位置之后的元素就不需要再去查找比对了

二分法巧妙的利用了列表有序的特性，每一次查找，都将查找范围缩小为原来的一半

---

 

3、示例代码

 

#coding=utf-8

def search(lst,targt,start,end):
    if start > end:
        return -1

    mid = (start + end)/2
    if targt == lst[mid]:
        return mid
    elif targt > lst[mid]:
        return search(lst,targt,mid+1,end)
    else:
        return search(lst,targt,start,mid-1)


def binary_search(lst,targt):
    start = 0
    end = len(lst) -1
    index = search(lst,targt,start,end)
    return index

lst = [1,3,6,7,8,10,15,18]
print binary_search(lst,15)
print binary_search(lst,9)