二分插入、bisect
2024-08-22 10:01:37
在一个有序序列(从小到大)中查找一个元素
每次将元素与序列中间位置的元素进行比较
如果大于中点,则在后半段。如果小于中点,则在前半段。以此类推
时间复杂度为O(logn)
有一个无序序列[37, 99, 73, 48, 47, 40, 40, 25, 99, 51],对其先排序输出新列表。
分别插入20、40、41、100到这个新序列中合适的位置,保证其有序。
origin = [37, 99, 73, 48, 47, 40, 40, 25, 99, 51]
origin = sorted(origin)
# print(origin)
# [25, 37, 40, 40, 47, 48, 51, 73, 99, 99]
# 有重复时从左边插入
def insert_sort(origin:list, num):
low = 0
high = len(origin)
while low < high:
mid = (low + high)//2
# 如果大于中点,则在后半部分
if num > origin[mid]:
low = mid + 1
# 否则在前半部分
else:
high = mid
origin.insert(low, num)
for num in (20, 40, 41, 100):
insert_sort(origin, num)
print(origin)
# [20, 25, 37, 40, 40, 40, 41, 47, 48, 51, 73, 99, 99, 100]
origin = [37, 99, 73, 48, 47, 40, 40, 25, 99, 51]
origin = sorted(origin)
# 有重复时从右边插入
def insert_sort(origin:list, num):
low = 0
high = len(origin)
while low < high:
mid = (low + high)//2
if num < origin[mid]:
high = mid
else:
low = mid + 1
origin.insert(low, num)
for num in (20, 40, 41, 100):
insert_sort(origin, num)
print(origin)
# [20, 25, 37, 40, 40, 40, 41, 47, 48, 51, 73, 99, 99, 100]
bisect模块
bisect包含两个主要函数 bisect和insort,都是基于二分法实现
- bisect: bisect_right的别名,返回插入点位置,有重复时返回右边插入点
- bisect_left: 返回插入点位置,有重复时返回左边插入点
- insort: insort_right的别名,默认有重复时从右边插入
- insort_left: 有重复时从左边插入
import bisect
origin = [37, 99, 73, 48, 47, 40, 40, 25, 99, 51]
origin = sorted(origin)
for num in (20, 40, 41, 100):
bisect.insort_left(origin, num)
print(origin)
# [20, 25, 37, 40, 40, 40, 41, 47, 48, 51, 73, 99, 99, 100]
判断学生成绩,成绩等级A-E,其中,90分以上为A,80-89为B,70-79为C,60-69为D,50-59为E
breakpoints = [60, 70, 80, 90]
grades = 'EDCBA'
index = bisect.bisect(breakpoints, 55)
print(grades[index])
# E
参考:
https://zh.wikipedia.org/wiki/二分搜索算法
https://docs.python.org/3/library/bisect.html
最新文章
- Other linker flags
- 使用python的subprocess启动windows程序提示WindowsError: [Error 6] The handle is invalid
- 再学C++之C++中的全部关键字
- Sqoop 命令
- HDU 3642 Get The Treasury 线段树+分层扫描线
- PHP: 使用CURL访问FTP
- bootstrap datetimepicker 时间段选择限制
- Lucene和jackson冲突
- C语言IO操作总结
- Android源码之Gallery专题研究(1)
- How-to go parallel in R – basics + tips(转)
- 为神马精确Sprite的碰撞形状不通过简单的放大Sprite的尺寸来解决?
- linux下oracle启动关闭
- SQL SERVER 2008远程数据库移植到本地的方法
- Linux 定时任务调度(crontab命令)
- vue.js学习第一天,了解vue.js
- Spring 配置文件
- WebRequest + Https + 憑証錯誤 = 作業逾時
- Ural 2040. Palindromes and Super Abilities 2 回文自动机
- eg_6
热门文章
- Mybatis教程-实战看这一篇就够了
- 【react】使用 create-react-app 构建基于TypeScript的React前端架构----上
- Terraform:简介
- 一文让你完全弄懂Stegosaurus
- 利用Git工具将本地创建的项目上传到Github上
- 转:SpringMVC之类型转换Converter(GenericConverter)
- libmysqlclient.so.16: cannot open shared object file: No such file or directory
- MySQL高可用架构-MHA环境部署记录
- python基础学习笔记(十一)
- 路由嵌套 active