【算法图解】二分查找

算法表现

二分查找是计算机学习中比较基础的算法，具体算法表现如下：

1. 排序，将要查找的一串数字从小到大或者从大到小进行排序。
2. 寻找该数字位置，取出正中间的数字，与要查找的数字比大小，大了就扔掉后面的一串数字，小了就扔掉前面的一串数字
3. 重复第二步，直到找到想要的数字。

代码表现

def binary_search(list, item):
    list.sort()
    print list
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) / 2
        guess = list[mid]
        if  guess == item:
            return mid
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    return None

my_list = [3,1,5,9,7,19,15,13,17,11]

print binary_search(my_list,3)
print binary_search(my_list,-1)

算法运行时间

大O表示法，O表示的是操作数

• O(log n),对数时间，比如二分查找
• O(n),线性时间，比如简单查找
• O(n*logn)，快速排序
• O(n^2)，选择排序
• O(n!)，旅行商问题解决方法