二分查找

查找指定元素在列表（已排序）中的位置

题目：
给出一个已经排好序的列表，用二分查找方法查找指定元素在列表中的位置

分析：
二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。

实现：

def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (high - low) // 2 + low    # 避免(high + low) / 2溢出
        guess = list[mid]
        if guess > item:
            high = mid - 1
        elif guess < item:
            low = mid + 1
        else:
            return mid
    return None
    
mylist = [1,3,5,7,9]
myitem = 3
print(binary_search(mylist, myitem))

输出：

/home/zhanglei/PycharmProjects/untitled/venv/bin/python /home/zhanglei/catkin_ws/src/beginner_tutorials/scripts/t.py
1

Process finished with exit code 0