小白的算法初识课堂(part1)–二分查找法
121 浏览量
2020-12-21
01:20:39
上传
评论
收藏 80KB PDF 举报
小白的算法初识课堂小白的算法初识课堂(part1)–二分查找法二分查找法
学习笔记
学习书目：《算法图解》- Aditya Bhargava
二分查找法二分查找法
算法是一组完成任务的指令，任何代码片段都可视为算法。二分查找是一种算法，其输入是一个有序的元素列表（必须有序的
原因稍后解释）。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。
下面，我们玩一个猜数字游戏。我随便想一个1~100的数字，而你的目标是以最少的次数猜到这个数字。
简单查找
假设你从1开始依次往上猜，则每次猜测都只能排除一个数字，如果我想的数字是99，你得猜99次才能猜到！这是简单查找简单查找，
更准确的说法是傻找傻找。
二分查找法
假设你从50开始猜数字，下面是我们的对话：
#----第1轮----
你：猜50
我：小了
#----第2轮----
你：猜75
我：大了
#----第3轮----
你：猜63
我：大了
#----第4轮----
你：猜56
我：对啦！
我发现了，你每一次都猜余下数字的中间数字！比如，你猜50，我告诉你小了，你知道1 ～ 50都小了，所以就把1 ~ 50都排除，
再选取56 ~ 100 的中间数字75，我又告诉你大了，你就把75~100排除，以此类推…
那么，你用的这种方法就是二分查找法。
一般而言，对于包含n个元素的列表，用二分查找法最多需要log2nlog_2 nlog2n步，运行时间为对数时间；而简单查找法最多
则需要n步，运行时间为线性时间。
python实现
import math
def binary_search(my_list, item):
low = 0
high = len(my_list) - 1
while low item:
high = mid - 1
else:
low = mid + 1
return None
my_list = [2, 4, 6, 8, 10]
print(binary_search(my_list, 8))
控制台输出：
3
大大O表示法表示法
大O表示法是一种特殊的表示法，指出了算法的速度有多快。现在，我们用简单查找法和二分法来猜数字，假设一共有
10，100，10,000和1,000,000,000个数字，查找一个元素要耗费1毫秒:
评论0