当前位置: 首页 > 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…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

基于SpringBoot在线拍卖系统的设计和实现

摘 要 随着社会的发展&#xff0c;社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统&#xff0c;主要的模块包括管理员&#xff1b;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...