当前位置: 首页 > news >正文

【算法基础】插入排序与二分查找、升级二分查找

文章目录

  • 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 插入排序的思想 插入排序很类似于已有一副有序的扑克牌&#xff0c;不断…...

在Vue3中如何使用H.265视频流媒体播放器EasyPlayer.js?

H5无插件流媒体播放器EasyPlayer属于一款高效、精炼、稳定且免费的流媒体播放器&#xff0c;可支持多种流媒体协议播放&#xff0c;可支持H.264与H.265编码格式&#xff0c;性能稳定、播放流畅&#xff0c;能支持WebSocket-FLV、HTTP-FLV&#xff0c;HLS&#xff08;m3u8&#…...

基于51单片机的PM2.5监测系统设计—环境监测仪

基于51单片机的PM2.5监测系统 &#xff08;仿真&#xff0b;程序&#xff0b;原理图&#xff0b;PCB&#xff0b;设计报告&#xff09; 功能介绍 具体功能&#xff1a; 1.PM2.5传感器模块检测信息给单片机处理&#xff1b; 2.LCD1602实时显示PM2.5浓度和PM2.5报警阈值&#x…...

【C语言】指针篇-初识指针(1/5)

&#x1f308;个人主页&#xff1a;是店小二呀 &#x1f308;C语言笔记专栏&#xff1a;C语言笔记 &#x1f308;C笔记专栏&#xff1a; C笔记 &#x1f308;喜欢的诗句:无人扶我青云志 我自踏雪至山巅 文章目录 **内存和地址(知识铺垫(了解即可))**如何理解编址**指针变量*…...

【御控物联】物联网平台设备接入-JSON数据格式转化(场景案例四)

文章目录 一、背景二、解决方案三、在线转换工具四、技术资料 一、背景 物联网平台是一种实现设备接入、设备监控、设备管理、数据存储、消息多源转发和数据分析等能力的一体化平台。南向支持连接海量异构&#xff08;协议多样&#xff09;设备&#xff0c;实现设备数据云端存…...

stack和queue模拟实现

前言 上一期我们介绍了stack和queue的使用&#xff0c;本期我们来模拟实现一下他们&#xff01; 本期内容介绍 容器适配器 deque介绍 为什么stack和queue的底层选择deque为默认容器&#xff1f; stack 模拟现实 queue 模拟实现 什么是容器适配器&#xff1f; 适配器是一种设…...

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…...

分布式锁介绍

引言 分布式锁是一种用于协调不同进程或线程对共享资源的访问控制的机制。在分布式系统中&#xff0c;由于多个节点可能同时访问或修改同一资源&#xff0c;因此需要一个中心化的协调机制来确保资源的访问是有序的&#xff0c;避免数据不一致的问题。 分布式锁的特性&#xf…...

Unity 获取RenderTexture像素颜色值

拿来吧你~ &#x1f9aa;功能介绍&#x1f32d;Demo &#x1f9aa;功能介绍 &#x1f4a1;不通过Texture2D 而是通过ComputerShader 提取到RenderTexture的像素值&#xff0c;效率有提升哦&#xff01; &#x1f4a1;通过扩展方法调用&#xff0c;方便快捷&#xff1a;xxxRT.G…...

Tomcat以服务方式启动,无法访问网络共享目录问题

关于“Tomcat以服务方式启动&#xff0c;无法访问网络共享目录问题”解决方式如下&#xff1a; 1、通过doc命令【services.msc】打开本地服务找到&#xff0c;找到tomcat服务所在位置 2、右键打开Tomcat服务的属性 3、选择 登陆选项卡 4、选择“此账户”选项&#xff0c;并…...

SVN的介绍

首先SVN是什么&#xff1a; Apache下的一个开源的项目Subversion&#xff0c;通常缩写为 SVN&#xff0c;是一个版本控制系统。 版本控制系统是一个软件&#xff0c;它可以伴随我们软件开发人员一起工作&#xff0c;让我们编写代码的完整的历史保存下来。 目前它的各个版本的…...

ZYNQ-700呼吸灯

参考野火例程 实现呼吸灯即要调整led亮的占比时间&#xff0c;完成视觉上看起来由灭到亮或者由亮到灭的过程。 如果主频为50MHz&#xff0c;理论上一秒钟我们可以控制50_000_000次led的亮和灭&#xff0c;肉眼不可能分辨出来每一次亮灭&#xff0c;如果这50M我们设定为间隔一…...

UE5学习日记——制作多语言版本游戏,同时初步学习UI制作、多语言化、控制器配置、独立进程测试、打包配置和快速批量翻译等

所有的文本类&#xff0c;无论变量还是控件等都能实现本地化&#xff0c;以此实现不同语言版本。 在这里先将重点注意标注一下&#xff1a; 所有文本类的变量、控件等都可以多语言&#xff1b;本地化控制板中收集、编译时&#xff0c;别忘了编译这一步&#xff1b;支持批量复制…...

电脑重启后word文档空白或打不开,word无法自动修复,如何拯救

最近编辑word文档&#xff0c;写了好几个星期的内容随着电脑重启的一瞬间&#xff0c;灰飞烟灭&#xff0c;让我简直痛不欲生&#xff01; 好在&#xff0c;天无绝人之路&#xff0c;以下两个方法拯救了地球 第一&#xff0c;普通的文档word自动修复不好使的时候&#xff0c;…...

MVC和MVVM这两种设计模式的区别

一、MVC和MVVM是什么&#xff1f; MVC是Model-View-Controller的简写&#xff0c;Model就是模型&#xff0c;对应后端数据&#xff0c;View就是视图对应用户界面&#xff0c;Controller就是控制器&#xff0c;对应页面的业务逻辑。 MVC的工作机制原理就是&#xff0c;用户操作…...

淘宝app端商品详情数据采集(商品价格,商品库存,商品销量,商品优惠券)

在淘宝App端采集商品详情数据&#xff0c;包括商品价格、库存、销量以及优惠券信息&#xff0c;可以通过多种方式实现。以下是几种常见的方法&#xff1a; 使用淘宝开放平台API&#xff1a; 淘宝开放平台提供了一系列API接口&#xff0c;这些接口允许开发者获取淘宝商品的详细…...

第42篇:随机存取存储器(RAM)模块<一>

Q&#xff1a;本期开始我们分期介绍随机存取存储器&#xff08;RAM&#xff09;模块及其设计实现方法。 A&#xff1a;随机存储器RAM&#xff0c;即工作时可以随时从一个指定地址读出数据&#xff0c;也可以随时将数据写入一个指定的存储单元。 DE2-115开发板上的Cyclone IV …...

在Java中实现记录1000万用户连续7天登录的功能,可以使用Redis的Bitmap来跟踪每个用户的登录状态

在Java中实现记录1000万用户连续7天登录的功能&#xff0c;可以使用Redis的Bitmap来跟踪每个用户的登录状态。以下是一个简化的Java示例&#xff0c;使用了Jedis库作为Redis的Java客户端。 首先&#xff0c;确保你已经在项目中添加了Jedis的依赖。如果你使用Maven&#xff0c;…...

深入探讨VIVE OpenXR:为Unity开发者的全面指南

随着虚拟现实&#xff08;VR&#xff09;和增强现实&#xff08;AR&#xff09;技术的迅速发展&#xff0c;开发者们对于能够简化和优化沉浸式应用开发的工具需求日益增长。HTC Vive 作为行业内的领先品牌&#xff0c;其最新推出的 VIVE OpenXR 插件为Unity开发者提供了一个强大…...

【Altium Designer 20 笔记】PCB线宽与过孔尺寸

电源线&#xff1a;40mil1A&#xff08;一般翻倍给&#xff09;,地线比电源线粗一点即可&#xff1b;信号线&#xff1a;10-15mil 一、线宽 市电的火线和零线&#xff1a;80-100mil12V /24V 20mil~60mil 5V 20-30mil 3V 20-30mil GND 越宽越好20-30mil普通信号线 10mil-15mil…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

用鸿蒙HarmonyOS5实现中国象棋小游戏的过程

下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...

Matlab实现任意伪彩色图像可视化显示

Matlab实现任意伪彩色图像可视化显示 1、灰度原始图像2、RGB彩色原始图像 在科研研究中&#xff0c;如何展示好看的实验结果图像非常重要&#xff01;&#xff01;&#xff01; 1、灰度原始图像 灰度图像每个像素点只有一个数值&#xff0c;代表该点的​​亮度&#xff08;或…...

Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程

鸿蒙电脑版操作系统来了&#xff0c;很多小伙伴想体验鸿蒙电脑版操作系统&#xff0c;可惜&#xff0c;鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机&#xff0c;来体验大家心心念念的鸿蒙系统啦&#xff01;注意&#xff1a;虚拟…...

【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)

旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据&#xff01;该数据集源自2025年4月发表于《地理学报》的论文成果…...