1. 算法简介

1.2 二分查找

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置; 否则返回null 。

使用二分查找时，最多需要检查log n 个元素。

仅当列表是有序的时候，二分查找才管用。

完整代码如下：

def binary_search(list, item):
    low = 0
    high = len(list)-1
    while low <= high:
        mid = int((low+high)/2)
        guess = list[mid]
        if guess == item:
            return mid
        elif guess < item:
            low = mid + 1
        else:
            high = mid - 1
    return None
    
my_list = [1,3,5,7,9]
print(binary_search(my_list, 3))
print(binary_search(my_list, -1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

一般而言，应选择效率最高的算法，以最大限度地减少运行时间或占用空间。

最多需要猜测的次数与列表长度相同，这被称为线性时间 (linear time)。

简单查找：线性时间 O(n)
二分查找：对数时间 O(log n)

1.3 大O表示法

大O表示法是一种特殊的表示法，指出了算法的速度有多快。

大O表示法指出了最糟情况下的运行时间。

5种大O运行时间：

• O (log n )，也叫对数时间 ，这样的算法包括二分查找。
• O (n )，也叫线性时间 ，这样的算法包括简单查找。
• O (n * log n )，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
• O ($n^2$ )，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
• O (n !)，这样的算法包括接下来将介绍的旅行商问题的解决方案 ——一种非常慢的算法。

按从快到慢的顺序列出了使用这些算法绘制网格所需的时间:

算法的速度指的并非时间，而是操作数的增速。

谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。

算法的运行时间用大O表示法表示。

References:
《 算法图解》—— 第1章 算法简介