在一个列表当中我们可以进行线性查找也可以进行二分查找, 即通过不同的方法找到我们想要的数字, 线性查找即按照数字从列表里一个一个从左向右查找, 找到之后程序停下. 而二分查找的效率往往会比线性查找更高.
一. 二分查找的步骤
二分查找的步骤首先是将列表进行升序或者降序排列, 否则无法进行数字的比较, 也就无法进行二分查找. 然后找到一个列表的中间数值 (mid), 如果列表当中的数字和为基数, 则为最中间的那个数. 如果为偶数, 则为最中间的那两个数的左边那一个, 比如说我们有一个列表,[1,2,3,4,5,6], 列表当中的数字为偶数个, 那么 mid 则是 3. 找到 mid 之后, 再和我们需要查找的数字进行比较, 如果比我们需要查找的数字要小, 那么就让 low=mid+1, 即在 Mid 的右边一个, 如果比我们需要的数字要大, 则让 high=mid-1, 在 high 的左边一个, 利用夹逼法直到 mid 等于 var 的时候这个时候在返回 mid 的值, 这个值就是我们数字所在的顺序数, 在列表当中的 order 或称 index(索引). 我们下面一张图来表示二分查找的步骤, 下面是举了一个最为简单的列子, 数字的个数仅为 4 个, 且为 1,2,3,4.
假设我们想要找的数字为 3 的 index, 因此首先在第一次循环当中, 1=low,4=high,mid=2, 我们令 var=3, 也就是我们想要找的数为 var, 发现这个数的数值是比 mid 的数值更大的, 因此 low=mid+1, 此时 mid 所代表的数值变成了 3. 紧接着我们进行下一次循环, 我们发现 var 和 mid 是相等的, 因此返回 mid 的数值 (并非 mid 所对应在列表当中的数值, 而是 mid 自己的值), 这样就可以得到 var 的索引值了! 实现的程序如下:
- # 首先咱们来看一个线性查找, 这个的效率比较低
- li = [1,2,3,4,0,4,2,3]
- # print(6 in li)# 这个就是线性查找, 看 6 是否在里面
- # print(li.index(6))# 看 6 在第几个 index
- li.sort()
- print("进行排序之后的列表为:{}".format(li))
- def bin_search(li, var):
- low = 0
- high = len(li) - 1
- while low<=high:# 这里不能够使用 while true!! 不然输入一个不存在的值的话就会导致 mid 做了加减法后 low 比 high 大或者 high 比 Low 小, 失去了比较的意义
- mid = (low + high) // 2
- if li[mid] == var:
- return mid
- elif li[mid] <var:
- low = mid + 1
- else:# li[mid]> var
- high = mid - 1
- return -1
- # 二分查找的时间复杂度为 log(n)
- if __name__ == "__main__":
- print(bin_search(li, 3))
在程序当中需要注意的是循环 while 的判断条件是 low<=high, 因为如果在输入的值 var 不属于列表的情况下, 运算到最后 low 就会大于 high, 这种情况下是应该直接返回 - 1 的, 而不是继续运算到无穷无尽. 在这个程序当中我们设定了列表 li, 并通过定义二分查找函数来执行二分查找的过程. 程序也很通俗易懂, 和之前我们讲过的二分查找的步骤是一样的, 下面我们来看一个利用二分查找的例题:
二. 例题
这个例题节选自悉尼大学 "Python 编程" 这门课的每周同步编程练习, 题目是这样的:
输入一个序列, 然后让整个序列变成一个有序的列表, 最后找到数字 8 在这个列表当中的位置, 我们可以使用二分查找来做这道题目, 标准的 Example 如下:
现在我们使用二分查找算法来实现这个问题, 首先是输入的字符串用 input() 函数来进行接收, 但是接收之后的数字是字符串, 我们需要使用 split() 函数将其每一个元素通过间隔开, 由于使用了 split() 函数, 因此就会自己动返回一个列表, 不过里面每一个数字也还是 string 型, 我们再利用一个 for 循环将其改变为 int 型, 再重新灌入一个列表当中, 形成 interger 型的列表, 也就是我们第二个的输出结果, 最后运用咱们刚才的二分查找法, 得到数字 8 的 index 值, 程序如下:
- def binary_search(list, var):
- low = 0
- high = len(list)-1
- while low <= high:
- mid = (low+high)//2
- if list[mid] == var:
- return mid
- elif list[mid] < var:
- low=mid+1
- else:
- high=mid-1
- return -1
- a = input("Enter some integers:")
- a = a.split(",")
- print(a)
- ls = []
- for i in a:
- b = int(i)
- ls.append(b)
- print("我们得到的数组是:{}".format(ls))
- # 将列表进行升序排列, 这样才可以使用二分查找算法
- ls.sort()
- print(ls)
- if __name__ == "__main__":
- print(binary_search(ls,5))
输出结果如下:
- E:\conda\python.exe F:/computer/datast/T4Q6P4.py
- Enter some integers:23,4456,234,67,5
- ['23', '4456', '234', '67', '5']
我们得到的数组是:[23, 4456, 234, 67, 5]
- [5, 23, 67, 234, 4456]
- 0
今天的教程就到这里了! 希望你看了之后会有收获!
来源: https://www.cnblogs.com/geeksongs/p/12547708.html