二分查找算法二分查找算法

点击蓝字“莫名Coder”关注我哟
加个“星标★”，每日良时，好文必达！

文章图片

算法与数据结构
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
时间复杂度时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。时间复杂度常用大O符号表述
空间复杂度 【二分查找算法】空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记作S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。
用户登录问题
数据库存放了所有用户的登录账号和密码，假如我们登录淘宝，用户ID为：taobao

方法一：对数据中的每个数据进行匹配找到结果是否一致

很明显方法一效率低下，用户量在极少的情况下，还可行；但是如果有几十万数据，那么需要更多的时间进行匹配

方法二：预先对数据库中所有的数据按照字母排序，接着从数据可能中间开始查找，通过二分查找算法不断缩小范围

如果系统数据非常少只有16个，两种查找方法16次匹配和log2 16 = 4 次匹配的区别，假设我们用1000万用户，两种方式就是1000万次匹配和24次匹配的区别(log2 10000000=23.25)
什么是对数？你可能就不知道什么是对数，但是记得什么是幂。log10 100 相当于问："将多少的10相乘的结果是100"。答案是两个，因此：log10 100 = 2
二分查找算法学习二分查找算法之前，我们需要知道数组，python语言中就是列表。即数组中，假设从0开始编号，第一个元素位置为#0，第二个则是#1，依次类推。
例如：

文章图片

上图就是我们需要查找的数组部分，那么就可以知道low的起始值为0，high则为数组的长度减去1。

low = 0 high = len(list) - 1

每次需要猜取中间的元素。

mid = (low + high) // 2 # 如果mid不是一个偶数，我们采用向下取整 guess = list[mid]

如果猜的数字小了，就相应修改low的值，如果猜的数字大了，就修改high的值，完整的代码如下：

def find_search(list, item): # list传入的数组或者列表 # item则是传入查找列表的部分元素 low = 0 high = len(list) - 1 while low <= high: mid = (low + high) // 2 guess = list[mid] if guess == item: return mid if guess > item: high = mid - 1 else: low = mid + 1return Nonemy_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]print(find_search(my_list, 2))

运行时间二分查找中，我们简单查了9个数据，并没有发现快多少。如果是一个几百万的数据，不使用算法要猜几百万次。换而言之，猜的次数和列表长度一致，这就是线性时间。