3.26

算法图解笔记——Chapter 1 Intro
Author: Seven Zou
Email: [email protected]
Language: Python2.7

---

1.2 二分查找

二分查找是一种算法，其输入是一个有序的元素列表（必须有序的原因稍后解释）。 例如：查找1—100的数字 目标是以最少的次数猜到这个数字。每次猜测后，三种结果：大了、小了、对了。

• 1.假设从1往上猜 猜到99:
  - 1…
  - 2…
  - 3…
  - …每次只能猜测一个数字。
• 2.而如果从50开始猜:
  - 50 -> 小了（排除了一半的数字）
  - 75 -> 大了（又排除了一半）
  - 63 -> 大了（又排除了一半）
  - 57 -> 对了

一般而言，对于包含n个元素的列表，用二分查找最多需$log_2^n$log2n​，而简单查找最多需要n步
Note：仅当列表是有序的时候，二分查找才管用。例如，电话簿中的名字是按字母顺序排列的，因此可以使用二分查找来查找名字。如果名字不是俺顺序排列的，结果将会如何呢
编写执行二分查找的Python代码。实例中使用了数组（后序介绍）。
可将一系列元素存储在一系列相邻的桶（bucket），即数组中。这些桶从0开始编号：
第一个桶的位置为#0，
第二个桶的位置为#1，
第三个桶为#2，
以此类推。
函数binary_search接受一个有序数组和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。你将跟踪要在其中查找的数组部分——开始时为整个数组。

#-*- coding: utf-8 -*-     
def binary_search(list, item):  # list数据包，目标元素item 注意写函数开头不能为数字，必须带冒号：     
low = 0  # 低索引     
high = len(list) - 1  # low和high用于跟踪要在其中查找的列表部分 | 高索引为 len - 1（初始低索引为0）     
while low <= high:  # 只要范围没有缩小到之包含一个元素         
# mid = (low +high)         
mid = int((low + high) / 2)  # 就检查中间的元素 （书中错误，已更正）         
guess = list[mid]   # 获取中间元素         
if guess == item:  # 找到了元素 guess 即为 目标元素 item 则返回 索引 mid             
return mid         
if guess > item:  # 猜的数字大了 将高索引更改为 mid - 1             
high = mid - 1         
else:  # 猜的数字小了 将低索引更改为 low + 1             
low = mid + 1     
return None  # 没有指定的元素   my_list = [1, 3, 5, 7, 9]  
# Test
print(binary_search(my_list, 3))  # => 1 别忘了索引从0开始，第二个位置的索引为1 
print(binary_search(my_list, -1))  # => None 在python中，None表示空，它意味着没有找到指定的元素 

1.3 大O表示法

大O表示法指出了算法有多快。例如，假设列表包含n个元素。简单查找需要检测每个元素，因此需要执行n次操作。使用大O表示法，这个运行实际为 O(n)。大O表示法指的并非以秒为单位的速度。

• 对数时间——i.e.二分查找
• 线性时间——i.e.简单查找
• 一种速度较快的排序算法
• 一种速度较慢的排序算法
• 一种非常慢的算法——i.e.旅行商问题