Python实现二分查找算法
程序员文章站
2024-03-19 15:28:04
...
二分查找算法
二分算法是一种效率比较高的查找算法,其输入的是一个有序的元素列表,如果查找元素包含在列表中,二分查找返回其位置,否则返回NONE
想象一个场景:
我随便想1~100中的数字,你的目标是以最少的次数猜中我所想的数字,那么你会怎么做呢?
- 你可能会从1开始以此往上猜,直到猜中数字,这是一种简单查找算法,每次猜测只能排除一个数字
- 你可能从50开始猜,我告诉你大了或者小了,这样每猜一次,都会将剩余的数字排除掉一半,不管我心里想的是哪个数字,你在7次之内都能够猜到,因为每次猜测都将排除很多数字!
相比之下,第二种方法会更加省时,这种算法叫做二分算法,又称折半查找。
对于要搜索的元素越多,二分查找速度比简单查找快的更多 这是二分查找算法的优点,但二分算法也有缺点,二分算法只针对有序的列表,这样插入和删除就会很困难,因此,折半查找方法只适合不经常变动的有序列表
Python实现二分算法
# 二分算法是一种高效的查找算法,针对有序的数列
def binary_search(my_list, num):
"""
二分算法
:param my_list: 有序列表
:param num: 要查找的元素
:return: 存在返回下标 不存在返回NONE
"""
low = 0
high = len(my_list) - 1
while low <= high:
mid = int((low + high) / 2)
guess = my_list[mid]
if guess == num:
return mid
elif guess > num:
# 说明猜大了
high = mid - 1
else:
low = mid + 1
return None
def main():
"""主函数"""
my_list = [1, 3, 5, 7, 9] # 有序列表
num = 2 # 要猜测的数字
print(binary_search(my_list, num))
if __name__ == '__main__':
main()
返回num下标 1
二分查找算法运行时间:O(log2 n )
简单查找算法运行时间:O(n)