第一章 算法简介
算法是一组完成任务的指令。
二分查找
二分搜索，也称折半搜索、对数搜索，是一种在有序数组中查找某一特定元素的搜素算法。
利用二分查找，猜想 1-100中的一个数字，7 次之内都能猜到
1.png
假设你要在字典中查找一个单词，而该字典包含 240000单词，只需要 18步 ！
2.png
对于包含 n 个元素的列表，用二分查找最多需要 log2n，而简单查找最多需要 n 步。
PS: 二分查找只在有序的数组中有效
实例
给定一个有序（非降序）数组A，可含有重复元素，求最小的i使得A[i]等于target，不存在则返回-1。
时间复杂度要求为：O(log2n)
def binarySearch(list, item):
low = 0
high = len(list) - 1
while low <= high:
mid = (high + low) // 2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid -1
else:
low = mid + 1
return -1
if __name__ == '__main__':
li = [1, 3, 5, 7, 9]
print(binarySearch(li, 3)) # 1
print(binarySearch(li, 10)) # -1
大 O 表示法
"大O记法": 对于单调的整数函数 f，如果存在一个整数函数 g 和实常数 c>0，使得对于充分大的 n 总有 f(n)<=c*g(n)，就说函数 g 是 f 的一个渐进函数 (忽略常数)，记为 f(n) = O(g(n))。也就是说，在趋向无穷的极限意义下，函数 f 的增长速度受到函数 g 的约束，即函数 f 与 函数 g 的特征相似。
时间复杂度: 假设存在函数 g，使得算法 A 处理规模为 n 的问题示例所用时间为 T(n) = O(g(n))，则称 O(g(n)) 为算法 A 的渐进时间复杂度，简称时间复杂度，记为 T(n)。 一般考虑的都是最坏时间复杂度
这些理论的东西看看就好，知道有这么个东西就可以了
一些常见的大 O 运行时间:
- O(logn)，也叫对数时间，这样的算法包括二分查找；
- O(n)，也叫线性时间，这样的算法包括简单查找；
- O(n*logn)，这样的算法包括快速排序 ---- 一种较快的排序算法
- O(n2)，这样的算法包括选择排序 ---- 一种较慢的排序算法
- O(n!)，这样的算法包括文中讲到的旅行商问题的解决方案
3.png
练习
使用大 O 表示法给出下述各种情形的运行时间。
- 在电话薄中根据名字查找号码。(个人觉得应该是有序的) O(log2n)
- 在电话薄根据电话号码找人(提示: 你必须查找整个电话薄) O(n)
- 阅读电话薄每个人的电话号码。 O(n)
- 阅读电话薄中姓名以 A 打头的人的电话号码。O(n)
小结
- 二分查找的速度比简单查找快得多；
- O(logn) 比 O(n) 快。需要搜索的元素越多，前者比后者就快得越多；
- 算法运行时间并不以秒为单位；
- 算法运行时间是从增速的角度度量的；
- 算法运行时间用大 O 表示法表示。
