算法图解: 1.二分查找
2021/8/11 12:36:31
本文主要是介绍算法图解: 1.二分查找,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
""" @project: books @file: binary_search.py @time: 2021/08/11 @software: PyCharm @author: zy7y 二分查找算法: 二分查找是一种算法,其输入是一个有序的元素列表(必须有序的原因稍后解释)。如果要 查找的元素包含在列表中,二分查找返回其位置;否则返回null 猜大小游戏 给定 1 ~ 100 中的某个数字 55 非二分查找: 从 1 依次 向上猜到 55 共计猜55次 二分查找:从50开始猜, 次数就会少很多(每次猜中间的数字),共计 7次 50 -> 小了 75 -> 大了 63 -> 大了 56 -> 大了 53 -> 小了 54 -> 小了 55 -> 对了 对于包含n个元素的列表,用二分查找最多需要log2n步,而简单查找最多需要n步。 即 8个元素的列表, 使用二分查找需要 log2 8 = 3 对数: log10100相当于问“将多少个10相乘的结果为100”。答案是两个: 10 × 10 = 100。因此, log10100 = 2。 时间(大O): O(logn) 二分查找的速度比简单查找快得多。 O(log n)比O(n)快。需要搜索的元素越多,前者比后者就快得越多。 算法运行时间并不以秒为单位。 算法运行时间是从其增速的角度度量的。 算法运行时间用大O表示法表示。 """ from typing import List, Union def binary_search(arr: List[int], item) -> Union[int, None]: """ 二分查找,传入一个有序序列,和序列中某个元素值,快速找到其下标 :param arr: 有序列表 :param item: 查找元素值 :return: 找到返回下标,找不到返回None """ low = 0 # 起点 high = len(arr) - 1 # 终点 while low <= high: # 起点小于终点 循环 mid = (low + high) // 2 # 中间值 guess = arr[mid] # 取到中间值(下标)对应的value if guess == item: return mid # 相等 return 下标 if guess > item: high = mid - 1 # 值大,把终点调整为 中间值 - 1 else: low = mid + 1 # 值小, 把起点调整为 中间值 + 1 return None my_list = [i for i in range(1000) if i % 2 == 1 ] print(binary_search(my_list, 55555555)) # => 1
这篇关于算法图解: 1.二分查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求