二分查找介绍

Created: March 9, 2022 10:45 AM
Introduction: 二分查找：又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
Source: 原创
Tags: 算法专栏

什么是二分查找

• 二分查找：又叫折半查找，从有序列表的初始候选区li[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
• 时间复杂度：$O(logn)$

def binary_search(li, val):left = 0  # 有序列表最左边right = len(li) - 1  # 有序列表最右边while left <= right:  # 候选区mid = (left + right) // 2   # 整除if li[mid] == val:return midelif li[mid] > val: # 待查找的值在mid左侧right = mid - 1else:# li[mid] < val 待查找的值在mid右侧left = mid + 1else:return None

Python内置列表查找函数 index()

• index() 是线性表查找，原因：

  二分查找需要有序序列，如果是无序列表需要先排序，排序的时间消耗得考虑进去；

  如果只用一次查找函数，先排序可能会得不值得。

• index() 函数用于从列表中找出某个值第一个匹配项的索引位置。

• 用法:

list.index(value)# 返回值：
# 该方法返回查找对象的索引位置，如果没有找到对象则抛出异常。

相关参考

清华大学博士讲解Python数据结构与算法：https://www.bilibili.com/video/BV1uA411N7c5?p=10