高性能二分查找算法Python精简版
2023-09-11 14:17:14 时间
在已有排序的列表中,如果需要高性能查找特定数,使用二分查找;即使是无序列表,也可以先采用O(nlogn)时间复杂度下排序,再二分查找也是不错的选择
def binary_search(li, left, right, num): while left < right: mid = (left + right) // 2 if li[mid] == num: return mid elif li[mid] > num: right = mid else: left = mid if __name__ == '__main__': data = [e for e in range(1000)] res = binary_search(data, 0, len(data), 23) print(res, data[res])
功能:第一个大于等于target的位置:
# the first >= n position def binary_search(nums, target): if not nums: return start, end = 0, len(nums)-1 while start + 1 < end: mid = start + (end-start) // 2 print(start, mid, end) if nums[mid] == target: end = mid elif nums[mid] > target: end = mid else: start = mid if nums[start] == target: return start if nums[end] == target: return end data = [1,2,4,4,4,6,9,22] print(binary_search(data, 4))
功能:第一个大于target的位置:
def binary_search(nums, target): if not nums: return start, end = 0, len(nums)-1 while start + 1 < end: mid = start + (end-start) // 2 print(start, mid, end) if nums[mid] == target: start = mid elif nums[mid] > target: end = mid else: start = mid if nums[start] == target: return start+1 if nums[end] == target: return end + 1 data = [1,2,4,4,4,6,9,22] print(binary_search(data, 4))
相关文章
- Python脚本扫描给定网段的MAC地址表(scapy或 python-nmap)
- 零基础教你快速入门Python怎么学python入门?python新手学习路线
- python强大之处在哪里?为什么那么多人喜欢Python?
- python configParser配置文件模块
- Python 异常
- 基于python源码的啸叫抑制算法解析
- 《Python机器学习——预测分析核心算法》——第1章 关于预测的两类核心算法
- python 朴素算法
- Python数据可视化 Pyecharts 制作 Grid 组合组件
- LeetCode 上1769号 面试编程题,python编程
- TF-IDF的算法原理以及Python实现
- Python学习---Django的基础操作180116
- 华为OD机试 -最少数量线段覆盖(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -乱序整数序列两数之和绝对值最小(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 删除指定目录(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 服务依赖(Python)| 真题+思路+考点+代码+岗位
- 基于皮尔逊相关系数的用户相似推荐算法python实现
- 电商 Python 淘宝主图下载 淘宝详情图下载 考拉海购主图下载