前言

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法是一组完成任务的指令。任何代码片段都可视为算法。

二分查找

我相信大家可能都看过或者玩过一个游戏——数字炸弹，在一个数字范围内，有一个数字作为炸弹，谁猜中这个炸弹就要被惩罚。
规则是猜中被惩罚，那我们改一改，猜中了有奖励。此时你的目标就是以最少的此次数猜中这个数字，你每次猜测后，我会说小了，大了或对了。假设我们以1-100为范围，你从1开始依次往上猜，那么这个过程就会是这样

而这便是简单查找，也可以说是傻找，运气好你可能一次就能猜对，运气差，你可能得猜99次。
下面是一种更好得查找方式，也就是二分查找，每次猜数我们从一半开始，这样每次就能排除一半的数字。


而这我们最多只需要七次便能猜到。
如果一个列表，里面有240000个元素，我们通过简单查找，如果要查找的元素在列表尾部，可能需要240000步，但通过二分查找，只需要18步,即对包含n个元素的列表，用二分查找，最多只需要log2n步，而简单查找需要n步，但仅当列表是有序的，二分查找才适用。
我们用python代码来实现看看

# @Time:2022/1/2614:50
# @Author:中意灬
# @File:二分查找.py
# @ps:tutu qqnum:2117472285

#二分查找
import time
def Binary_search(lis,item):
    low=0
    high=len(lis)-1#查找列表的范围

    while low<=high:#只要范围没缩小到0，就继续查找
        mid=(high+low)//2#中间元素
        if lis[mid]==item:#找到了元素
            return mid
        elif lis[mid]>item:#查找的值在mid的右侧
            high=mid-1
        else:
            low=mid+1#查找的值在mid的左侧
    return None#没有查找到元素

#简单查找
def Liner_search(lis,item):
    for i,v in enumerate(lis):
        if v==item:
            return i
    else:
        return None

if __name__ == '__main__':
    lis=list(range(10000))
    t1=time.perf_counter()
    print(Binary_search(lis, 520))
    t2=time.perf_counter()
    print('二分查找耗时:',t2-t1)
    t3=time.perf_counter()
    print(Liner_search(lis,520))
    t4=time.perf_counter()
    print('简单查找耗时:',t4-t3)

运行结果：

可以看出二分查找确实要快于简单查找，在列表元素越多，被查找元素越位于列表尾端，二分查找的效率更快，时间更短。二分查找的运行时间为对数时间或者log时间，那么当遇见其他算法的时候，我们该怎么表示它的运行时间或者运行快慢呢，接下来要说的是一种大O表示法。

时间复杂度

大O表示法

大O表示法事是一种特殊的表示方法，指出了算法的速度有多快，例如，一个列表包含n个元素。通过简单查询需要检查每个元素，因此执行了n次操作，使用大O表示法，这个运行时间为O（n），有人会问，为什么不使用时间秒，分钟什么的来表达或者记时，因为算法的运行时间是以不同的速度增加的，比如假设检查100个元素，需要100毫秒，而使用二分查找时，只需要7毫秒，那么此时我们心想二分查找的速度时简单查找的15倍，那么检查10亿个元素，只需要30x15=450毫秒，因为二分查找10亿个元素只需要30毫秒，但是这样时错误的，实际简单查找10亿个元素需要许多天，所以我们无法用秒来记速。
大O表示法让你能够比较操作数，他指出了算法运行时间的增速。
用大O表示法表示二分查找就是这样O（logn）

大O表示法指出了最糟糕情况下的运行时间，比如列表有n个元素，而我们所要查找的元素恰好位于第一个，那么简单查找的运行时间就为O（1）吗？显然不对的，简单查找的运行时间始终为O（n），一次就找到这是我们最想要的结果，但大O表示法说的时最糟糕的情况，你可以理解为大O表示法为一个保障，即你简单查找，最多查找的次数不会超过n。
一些常见的大O运行时间

• O（log n），也叫对数时间，二分查找就是这样的算法
• O（n），也叫线性时间，如简单查找
• O（n * log n），这样的算法包括快速排序——一种速度不错的排序算法
• O（n^2），这样的算法包括选择排序——一种速度较慢的排序算法
• O（n！），一种超级慢的算法，著名的旅行商问题
  
  小结：
• 算法的速度指的不是时间，而是操作数的增数
• 谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以怎样的增数增加
• 算法的运行时间用大O表示法
• 运行速度O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)，当需要搜索的元素越多，前者比后者越快
  小练习：
  使用大O表示法给出下列的运行时间

print('1')
print('2')
print('3')

答案：O（1），大O表示法表示程序的执行时间或占用空间随数据规模的增长趋势

for i in range(n):
    print('hello world')
    for i in range(n):
        print('hello world')

答案：O（n^2），因为表示的是增数，所以我们只需要保留最高介，即最高的数量级即可

while n>1:
    print(n)
    n=n/2

答案：O（n），而不是O（n/2），大O表示法不考虑乘以，除以，加上或减去的数字，如O（n+2）,O(n-2),O(n*2),O(n/2),这些都是错误的表示方法

空间复杂度

• 空间复杂度用来评估算法内存占用大小的式子
• 空间复杂度的表示方式于时间复杂度表示方式基本一样
  算法使用了几个变量：O(1)
  算法使用了长度为n的一维列表：O(n)
  算法使用了长度为n宽度为m的二维列表：O(mn)
• 但现在硬件技术的发展，时间复杂度比空间复杂度更加重视，即出现了‘空间换时间这个概念’

小结

• 二分查找的速度比简单查找的速度快得多
• 算法运行时间并不以秒为单位
• 算法运行时间是从其增速的角度来度量的
• 算法运行时间用大O表示法表示
• 空间复杂度与时间复杂度的表示方式基本一样