Python 二分查找:bisect库的使用
✅作者简介:人工智能专业本科在读,喜欢计算机与编程,写博客记录自己的学习历程。
🍎个人主页:小嗷犬的个人主页
🍊个人网站:小嗷犬的技术小站
🥭个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。
本文目录
- 简介
- bisect 库的使用
- bisect_left
- bisect_right
- insort_left
- insort_right
- 二分查找基础实现
简介
bisect 库是 Python 标准库中的一部分,它提供了二分查找的功能。二分查找是一种在有序列表中查找某一特定元素的搜索算法。它的时间复杂度为 O(logn)O(\log n)O(logn),比顺序查找的时间复杂度 O(n)O(n)O(n) 要有效率。
bisect 库的使用
bisect 库提供了 bisect_left、bisect_right、insort_left、insort_right四个函数,用于在有序列表中查找或插入元素。
bisect_left
bisect_left 函数用于在有序列表中二分查找某一位置,使得在该位置插入指定元素后仍保持有序,返回该位置,如果元素已经存在,则返回它的左边位置。
函数原型如下:
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
其中,a 是一个有序列表,x 是要查找的元素,lo 和 hi 是查找范围的左右边界,key 是一个函数,用于从列表中提取比较的键值。
示例:
# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查找元素 4 的位置
print(bisect.bisect_left(a, 4)) # 4
# 查找元素 6 的位置
print(bisect.bisect_left(a, 6)) # 5
bisect_right
bisect_right 函数用于在有序列表中二分查找某一位置,使得在该位置插入指定元素后仍保持有序,返回该位置,如果元素已经存在,则返回它的右边位置。
函数原型如下:
bisect.bisect_right(a, x, lo=0, hi=len(a), *, key=None)
其中,a 是一个有序列表,x 是要查找的元素,lo 和 hi 是查找范围的左右边界,key 是一个函数,用于从列表中提取比较的键值。
示例:
# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查找元素 4 的位置
print(bisect.bisect_right(a, 4)) # 4
# 查找元素 6 的位置
print(bisect.bisect_right(a, 6)) # 8
除此之外,bisect_right 还可以简写为 bisect :
# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 查找元素 4 的位置
print(bisect.bisect(a, 4)) # 4
# 查找元素 6 的位置
print(bisect.bisect(a, 6)) # 8
insort_left
insort_left 函数用于在有序列表中二分查找某一位置,使得在该位置插入指定元素后仍保持有序,然后将元素插入该位置,如果元素已经存在,则插入到它的左边位置。
函数原型如下:
bisect.insort_left(a, x, lo=0, hi=len(a), *, key=None)
其中,a 是一个有序列表,x 是要插入的元素,lo 和 hi 是查找范围的左右边界,key 是一个函数,用于从列表中提取比较的键值。
示例:
# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort_left(a, 4)
print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort_left(a, 6)
print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]
insort_right
insort_right 函数用于在有序列表中二分查找某一位置,使得在该位置插入指定元素后仍保持有序,然后将元素插入该位置,如果元素已经存在,则插入到它的右边位置。
函数原型如下:
bisect.insort_right(a, x, lo=0, hi=len(a), *, key=None)
其中,a 是一个有序列表,x 是要插入的元素,lo 和 hi 是查找范围的左右边界,key 是一个函数,用于从列表中提取比较的键值。
示例:
# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort_right(a, 4)
print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort_right(a, 6)
print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]
除此之外,insort_right 还可以简写为 insort :
# 导入 bisect 库
import bisect
# 有序列表
a = [1, 2, 3, 3, 5, 6, 6, 6, 8, 10]
# 插入元素 4
bisect.insort(a, 4)
print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 10]
# 插入元素 6
bisect.insort(a, 6)
print(a) # [1, 2, 3, 3, 4, 5, 6, 6, 6, 6, 8, 10]
insort 函数的实质是调用 bisect 函数获取插入位置,然后调用 list.insert 函数将元素插入到该位置。
二分查找基础实现
在 Python 中,我们可以使用 bisect 库来实现二分查找,但其只能根据元素的值和元素之间的比较关系来查找元素的位置,如果要根据元素的其他属性或其他关系来查找元素的位置,就需要自己实现二分查找了。
二分查找的基本模板如下:
def binary_search(nums, target):left, right = 0, len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return midelif nums[mid] < target:left = mid + 1else:right = mid - 1return -1
通过修改模板,我们可以根据更复杂的关系来查找元素。
示例:
852. 山脉数组的峰顶索引
符合下列属性的数组arr称为 山脉数组 :
arr.length >= 3- 存在
i(0 < i < arr.length - 1)使得:
arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]给你由整数组成的山脉数组
arr,返回任何满足arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1]的下标i。来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/peak-index-in-a-mountain-array
解
class Solution:def peakIndexInMountainArray(self, arr: List[int]) -> int:n = len(arr)left, right, ans = 1, n - 2, 0while left <= right:mid = (left + right) // 2if arr[mid] > arr[mid + 1]:ans = midright = mid - 1else:left = mid + 1return ans
相关文章:
Python 二分查找:bisect库的使用
✅作者简介:人工智能专业本科在读,喜欢计算机与编程,写博客记录自己的学习历程。 🍎个人主页:小嗷犬的个人主页 🍊个人网站:小嗷犬的技术小站 🥭个人信条:为天地立心&…...
性能优化之HBase性能调优
HBase是Hadoop生态系统中的一个组件,是一个分布式、面向列存储的内存型开源数据库,可以支持数百万列(MySQL4张表在HBase中对应1个表,4个列)、超过10亿行的数据存储。可用作:冷热数据分离HBase适合作为冷数据…...
图像金字塔,原理、实现及应用
什么是图像金字塔 图像金字塔是对图像的一种多尺度表达,将各个尺度的图像按照分辨率从小到大,依次从上到下排列,就会形成类似金字塔的结构,因此称为图像金字塔。 常见的图像金字塔有两类,一种是高斯金字塔࿰…...
08-Oracle游标管理(定义,打开、获取数据及关闭游标)
目标 1.确定何时需要显示游标2.声明、打开和关闭显示游标3.从显示游标中提取数据4.了解与游标有关的属性5.使用游标FOR循环检索游标中的数据6.在游标FOR循环的子查询中声明游标7.评估使用逻辑运算符结合在一起的布尔条件游标 1、在使用一个PL/SQL块来执行DML语句或只返回一行结…...
Python判断字符串是否包含特定子串的7种方法
目录1、使用 in 和 not in2、使用 find 方法3、使用 index 方法4、使用 count 方法5、通过魔法方法6、借助 operator7、使用正则匹配转自:https://cloud.tencent.com/developer/article/1699719我们经常会遇这样一个需求:判断字符串中是否包含某个关键词…...
aop实现接口访问频率限制
引言 项目开发中我们有时会用到一些第三方付费的接口,这些接口的每次调用都会产生一些费用,有时会有别有用心之人恶意调用我们的接口,造成经济损失;或者有时需要对一些执行时间比较长的的接口进行频率限制,这里我就简…...
Hive---窗口函数
Hive窗口函数 其他函数: Hive—Hive函数 文章目录Hive窗口函数开窗数据准备建表导入数据聚合函数window子句LAG(col,n,default_val) 往前第 n 行数据LEAD(col,n, default_val) 往后第 n 行数据ROW_NUMBER() 会根据顺序计算RANK() 排序相同时会重复,总数不会变DENSE…...
JavaSe第7次笔记
1. C语言里面,NULL是0地址。Java中null和0地址没关系。 2.数组可以做方法的返回值。 3.可以使用变量作为数组的个数开辟空间。 4.断言assert,需要设置。 5.排序:Arrays. sort(array); 6.查找: int index Arrays. binarySea…...
什么是 Service 以及描述下它的生命周期。Service 有哪些启动方法,有 什么区别,怎样停用 Service?
在 Service 的生命周期中,被回调的方法比 Activity 少一些,只有 onCreate, onStart, onDestroy, onBind 和 onUnbind。 通常有两种方式启动一个 Service,他们对 Service 生命周期的影响是不一样的。 1. 通过 startService Service 会经历 onCreate 到 onStart,然后处于运行…...
Redis部署
JAVA安装 mkdir /usr/local/javacd /usr/local/java/wget --no-check-certificate --no-cookies --header "Cookie: oraclelicenseaccept-securebackup-cookie" http://download.oracle.com/otn-pub/java/jdk/8u131-b11/d54c1d3a095b4ff2b6607d096fa80163/jdk-8u13…...
AT32F437制作Bootloader然后实现Http OTA升级
首先创建一个AT32F437的工程,然后发现调试工程配置这里的型号和创建工程选的型号不一致,手动更改一下,使用PW Link下载程序的话还要配置一下pyocd.exe的路径。 打开drv_clk.c文件的调试功能看下系统时钟频率。 项目使用的是AT32F437VMT7芯片&…...
Springboot项目启动初始化数据缓存
1.从Java EE5规范开始,Servlet中增加了两个影响Servlet生命周期的注解, PostConstruct和PreDestroy,这两个注解被用来修饰一个非静态的void()方法,被PostConstruct修饰的方法会在服务器加载Servlet的时候运…...
深度学习必备知识——模型数据集Yolo与Voc格式文件相互转化
在深度学习中,第一步要做的往往就是处理数据集,尤其是学习百度飞桨PaddlePaddle的小伙伴,数据集经常要用Voc格式的,比如性能突出的ppyolo等模型。所以学会数据集转化的本领是十分必要的。这篇博客就带你一起进行Yolo与Voc格式的相互转化&…...
数据、数据资源及数据资产管理的区别
整理不易,转发请注明出处,请勿直接剽窃! 点赞、关注、不迷路! 摘要:数据、数据资源、数据资产 数据、数据资源及数据资产的区别 举例 CRM系统建设完成后会有很多数据,这些数据就是原始数据,业务…...
标度不变性(scale invariance)与无标度(scale-free)概念辨析
文章目录标度标度种类名义标度序级标度等距标度比率标度常用标度方法不足标度不变性标度不变(Scale-invariant)曲线和自相似性(self-similarity)射影几何分形随机过程中的标度不变性标度不变的 Tweedie distribution普适性&#x…...
WMS仓库管理系统解决方案,实现仓库管理一体化
仓库是企业的核心环节,若没有对库存的合理控制和送货,将会造成成本的上升,服务品质的难以得到保证,进而降低企业的竞争能力。WMS仓库管理系统包括基本信息,标签,入库,上架,领料&…...
css常见定位、居中方案_css定位居中
一、 定位分类 1、静态定位 position:static;(默认,具备标准流条件) 2、相对定位 position:relative; 通过 top 或者 bottom 来设置 Y 轴位置 通过 left 或者 right 来设置 X 轴位置 特点: 相对定位不会脱离文档流相对于自…...
【微信小程序】-- 自定义组件 -- 创建与引用 样式(三十二)
💌 所属专栏:【微信小程序开发教程】 😀 作 者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! &…...
ArangoDB——AQL编辑器
AQL 编辑器 ArangoDB 的查询语言称为 AQL。AQL与关系数据库管理系统 (RDBMS)区别在于其更像一种编程语言,更自然地适合无模式模型,并使查询语言非常强大,同时保持易于读写。数据建模概念 数据库是集合的集合。集合存储记录,称为文…...
Lesson 9.1 集成学习的三大关键领域、Bagging 方法的基本思想和 RandomForestRegressor 的实现
文章目录一、 集成学习的三大关键领域二、Bagging 方法的基本思想三、RandomForestRegressor 的实现在开始学习之前,先导入我们需要的库,并查看库的版本。 import numpy as np import pandas as pd import sklearn import matplotlib as mlp import sea…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
