【算法基础】插入排序与二分查找、升级二分查找
文章目录
- 1. 插入排序
- 1.1 插入排序的思想
- 1.2 插入排序的实现
- 2. 普通二分查找
- 2.1 普通二分查找的思想
- 2.2 普通二分查找的实现
- 3. 升级二分查找
- 3.1 升级二分查找思想
- 3.2 升级二分查找实现
1. 插入排序
1.1 插入排序的思想

插入排序很类似于已有一副有序的扑克牌,不断地通过值比较,将新的扑克牌插入到有序的扑克牌中(通过将新的扑克牌和有序的扑克牌进行比较)。
插入排序在代码实现上可能和冒泡有点像,但从算法的时间复杂度上分析,插入排序会优于冒泡排序。插入排序在遇到如 [ 1 , 2 , 3 , 4 , 5 , 6 ] [1, 2, 3, 4, 5, 6] [1,2,3,4,5,6]这种数据排列时,时间复杂度是常数项
选择排序和冒泡排序的时间复杂度都是 O ( n 2 ) O(n^2) O(n2),这两种排序算法都是与数据排列无关的。在遇到上述那种数据排列时,还是会执行 n 2 n^2 n2次
1.2 插入排序的实现
def swap(arr, i, j):temp = arr[i]arr[i] = arr[j]arr[j] = tempif __name__ == '__main__':arr = [6, 3, 1, 4, 2, 5]print("原数组:", arr)for i in range(1, len(arr)):for j in range(i, 0, -1):if arr[j] >= arr[j - 1]:continueelse:swap(arr, j, j - 1)print("排序后的数组:", arr)
2. 普通二分查找
在一个有序数组中,找某个数是否存在
2.1 普通二分查找的思想
在一个有序数组中,通过不断将数组二分来寻找最小值。

2.2 普通二分查找的实现
if __name__ == '__main__':arr = [6, 3, 1, 4, 2, 5]print("原数组:", arr)arr = sorted(arr)print("排序后的数组:", arr)fN = 4low = 0high = len(arr) - 1print("想要找的数为:", fN)while True:mid = int((low + high) / 2)if mid == low or mid == high:print("数不存在")breakif arr[mid] == fN:flag = Trueprint("数存在,位于数组的第", mid, "位")break;elif arr[mid] > fN:high = mid - 1elif arr[mid] < fN:low = mid + 1
3. 升级二分查找
在一个有序数组中,找>=某个数最左侧的位置
3.1 升级二分查找思想
和普通二分很类似,就是一点点的差异

3.2 升级二分查找实现
if __name__ == '__main__':arr = [6, 3, 1, 4, 2, 5]print("原数组:", arr)arr = sorted(arr)print("排序后的数组:", arr)fN = 4low = 0high = len(arr) - 1print("想要找的数为:", fN)while True:if low > high:print("想要找的数最左侧位于数组的第", low, "位")mid = int((low + high) / 2)if mid == low or mid == high:print("数不存在")breakif arr[mid] >= fN:high = mid - 1elif arr[mid] < fN:low = mid + 1
相关文章:
【算法基础】插入排序与二分查找、升级二分查找
文章目录 1. 插入排序1.1 插入排序的思想1.2 插入排序的实现 2. 普通二分查找2.1 普通二分查找的思想2.2 普通二分查找的实现 3. 升级二分查找3.1 升级二分查找思想3.2 升级二分查找实现 1. 插入排序 1.1 插入排序的思想 插入排序很类似于已有一副有序的扑克牌,不断…...
在Vue3中如何使用H.265视频流媒体播放器EasyPlayer.js?
H5无插件流媒体播放器EasyPlayer属于一款高效、精炼、稳定且免费的流媒体播放器,可支持多种流媒体协议播放,可支持H.264与H.265编码格式,性能稳定、播放流畅,能支持WebSocket-FLV、HTTP-FLV,HLS(m3u8&#…...
基于51单片机的PM2.5监测系统设计—环境监测仪
基于51单片机的PM2.5监测系统 (仿真+程序+原理图+PCB+设计报告) 功能介绍 具体功能: 1.PM2.5传感器模块检测信息给单片机处理; 2.LCD1602实时显示PM2.5浓度和PM2.5报警阈值&#x…...
【C语言】指针篇-初识指针(1/5)
🌈个人主页:是店小二呀 🌈C语言笔记专栏:C语言笔记 🌈C笔记专栏: C笔记 🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅 文章目录 **内存和地址(知识铺垫(了解即可))**如何理解编址**指针变量*…...
【御控物联】物联网平台设备接入-JSON数据格式转化(场景案例四)
文章目录 一、背景二、解决方案三、在线转换工具四、技术资料 一、背景 物联网平台是一种实现设备接入、设备监控、设备管理、数据存储、消息多源转发和数据分析等能力的一体化平台。南向支持连接海量异构(协议多样)设备,实现设备数据云端存…...
stack和queue模拟实现
前言 上一期我们介绍了stack和queue的使用,本期我们来模拟实现一下他们! 本期内容介绍 容器适配器 deque介绍 为什么stack和queue的底层选择deque为默认容器? stack 模拟现实 queue 模拟实现 什么是容器适配器? 适配器是一种设…...
docker操作
1、容器生命周期管理命令 docker run docker run --name tomcat8 -d -p 28080:8080 tomcat:8.5.38 docker run -i --name hausf --network bridge --ip 172.17.0.10 ubuntu:20.04 /bin/bash docker run -d --name hausf --net host ubuntu:20.04 /bin/bash docker run…...
分布式锁介绍
引言 分布式锁是一种用于协调不同进程或线程对共享资源的访问控制的机制。在分布式系统中,由于多个节点可能同时访问或修改同一资源,因此需要一个中心化的协调机制来确保资源的访问是有序的,避免数据不一致的问题。 分布式锁的特性…...
Unity 获取RenderTexture像素颜色值
拿来吧你~ 🦪功能介绍🌭Demo 🦪功能介绍 💡不通过Texture2D 而是通过ComputerShader 提取到RenderTexture的像素值,效率有提升哦! 💡通过扩展方法调用,方便快捷:xxxRT.G…...
Tomcat以服务方式启动,无法访问网络共享目录问题
关于“Tomcat以服务方式启动,无法访问网络共享目录问题”解决方式如下: 1、通过doc命令【services.msc】打开本地服务找到,找到tomcat服务所在位置 2、右键打开Tomcat服务的属性 3、选择 登陆选项卡 4、选择“此账户”选项,并…...
SVN的介绍
首先SVN是什么: Apache下的一个开源的项目Subversion,通常缩写为 SVN,是一个版本控制系统。 版本控制系统是一个软件,它可以伴随我们软件开发人员一起工作,让我们编写代码的完整的历史保存下来。 目前它的各个版本的…...
ZYNQ-700呼吸灯
参考野火例程 实现呼吸灯即要调整led亮的占比时间,完成视觉上看起来由灭到亮或者由亮到灭的过程。 如果主频为50MHz,理论上一秒钟我们可以控制50_000_000次led的亮和灭,肉眼不可能分辨出来每一次亮灭,如果这50M我们设定为间隔一…...
UE5学习日记——制作多语言版本游戏,同时初步学习UI制作、多语言化、控制器配置、独立进程测试、打包配置和快速批量翻译等
所有的文本类,无论变量还是控件等都能实现本地化,以此实现不同语言版本。 在这里先将重点注意标注一下: 所有文本类的变量、控件等都可以多语言;本地化控制板中收集、编译时,别忘了编译这一步;支持批量复制…...
电脑重启后word文档空白或打不开,word无法自动修复,如何拯救
最近编辑word文档,写了好几个星期的内容随着电脑重启的一瞬间,灰飞烟灭,让我简直痛不欲生! 好在,天无绝人之路,以下两个方法拯救了地球 第一,普通的文档word自动修复不好使的时候,…...
MVC和MVVM这两种设计模式的区别
一、MVC和MVVM是什么? MVC是Model-View-Controller的简写,Model就是模型,对应后端数据,View就是视图对应用户界面,Controller就是控制器,对应页面的业务逻辑。 MVC的工作机制原理就是,用户操作…...
淘宝app端商品详情数据采集(商品价格,商品库存,商品销量,商品优惠券)
在淘宝App端采集商品详情数据,包括商品价格、库存、销量以及优惠券信息,可以通过多种方式实现。以下是几种常见的方法: 使用淘宝开放平台API: 淘宝开放平台提供了一系列API接口,这些接口允许开发者获取淘宝商品的详细…...
第42篇:随机存取存储器(RAM)模块<一>
Q:本期开始我们分期介绍随机存取存储器(RAM)模块及其设计实现方法。 A:随机存储器RAM,即工作时可以随时从一个指定地址读出数据,也可以随时将数据写入一个指定的存储单元。 DE2-115开发板上的Cyclone IV …...
在Java中实现记录1000万用户连续7天登录的功能,可以使用Redis的Bitmap来跟踪每个用户的登录状态
在Java中实现记录1000万用户连续7天登录的功能,可以使用Redis的Bitmap来跟踪每个用户的登录状态。以下是一个简化的Java示例,使用了Jedis库作为Redis的Java客户端。 首先,确保你已经在项目中添加了Jedis的依赖。如果你使用Maven,…...
深入探讨VIVE OpenXR:为Unity开发者的全面指南
随着虚拟现实(VR)和增强现实(AR)技术的迅速发展,开发者们对于能够简化和优化沉浸式应用开发的工具需求日益增长。HTC Vive 作为行业内的领先品牌,其最新推出的 VIVE OpenXR 插件为Unity开发者提供了一个强大…...
【Altium Designer 20 笔记】PCB线宽与过孔尺寸
电源线:40mil1A(一般翻倍给),地线比电源线粗一点即可;信号线:10-15mil 一、线宽 市电的火线和零线:80-100mil12V /24V 20mil~60mil 5V 20-30mil 3V 20-30mil GND 越宽越好20-30mil普通信号线 10mil-15mil…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
