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

基于java的社区生活超市管理系统

开发语言&#xff1a;Java 框架&#xff1a;ssm 技术&#xff1a;JSP JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09; 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclip…...

51单片机入门_江协科技_27~28_OB记录的自学笔记_AT24C02数据存储秒表

27. AT24C02(I2C总线) 27.1. 存储器介绍 27.2. 存储器简化模型介绍&#xff0c;存储原理 27.3. AT24C02介绍 •AT24C02是一种可以实现掉电不丢失的存储器&#xff0c;可用于保存单片机运行时想要永久保存的数据信息 •存储介质&#xff1a;E2PROM •通讯接口&#xff1a;I2…...

LeetCode-热题100:169. 多数元素

题目描述 给定一个大小为 n 的数组 nums &#xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的&#xff0c;并且给定的数组总是存在多数元素。 示例 1&#xff1a; 输入&#xff1a; nums [3,2,3] 输出&#xf…...

汽车维修类中译英的英语翻译

近年来&#xff0c;随着全球化的加速和汽车市场的不断扩大&#xff0c;汽车维修领域的交流与合作也日益频繁。汽车维修类中译英的英语翻译在汽车行业中扮演着至关重要的角色。那么&#xff0c;针对汽车维修类翻译&#xff0c;中译英的英语翻译有何技巧&#xff1f; 业内人士指出…...

java中的List,ArrayList和LinkedList集合

List集合&#xff1a; void add(int index, E element) Inserts the specified element at the specified position in this list (optional operation). 在此集合中的指定位置插入指定元素 E remove(int index) Removes the element at the specified position in this list (…...

RESTful API与Web应用程序构建:原理与实践

在现代Web开发中&#xff0c;RESTful API已经成为构建应用程序的核心组件之一。RESTful API不仅为前后端分离的开发模式提供了强有力的支持&#xff0c;还使得不同服务和应用之间的数据交互变得简单高效。本文将深入探讨RESTful API的原理&#xff0c;并展示如何使用它来构建We…...

输了,腾讯golang一面凉了

本月正值4月,是金三银四的找工作的最佳时机。同时竞争也是很大,因为每年这个时候快要毕业的大学生也进去了找工作的潮水中。 今天分享我的一位大佬朋友CC,勇闯腾讯golang的面试经历。 这次面试问题的方向主要集中在计算机基础个网络方面。 下面是主要问到的问题。 第一个…...

如何通过代码签名证书加强安全防护?

在当今数字化时代&#xff0c;安全防护是用户和企业保护其数据和应用程序免受恶意攻击的关键。代码签名证书是一种通过数字签名来验证软件代码来源和完整性的安全工具。通过对软件代码进行数字签名&#xff0c;代码签名证书可以加强安全防护&#xff0c;防止恶意软件和篡改攻击…...

Docker速成:新手变专家!

Docker介绍 容器历史 1、Chroot Jail 就是常见的chroot命令的用法。它在1979年的时候就出现了&#xff0c;被认为是最早的容器化技术之一。它可以把一个进程的文件系统隔离起来。 2、The FreeBSD Jail &#xff08;监狱&#xff09;实现了操作系统级别的虚拟化&#xff0c;他…...

numpy/arrayobject.h: No such file or directory

catkin编译时出现,numpy/arrayobject.h: No such file or directory 错误表明编译过程中找不到 NumPy 相关的头文件。这通常是因为环境中的 NumPy 没有被正确配置到包含路径中,或者 NumPy 没有被安装。以下是几个解决步骤来帮助你解决这个问题: 确认 NumPy 已安装 首先,确保…...

wordpress 前端 修改/搜狗网站排名软件

dump 0x8048000开始的19870字节到C:\FileName.dat.writemem C:\FileName.dat 8048000 L0n19870 转载于:https://www.cnblogs.com/XiaoHui/archive/2010/02/26/1674020.html...

如何在工信部网站注册/网络优化工程师证书

1.简介 shell脚本执行方式: Shell 是一个用 C 语言编写的程序&#xff0c;通过 Shell 用户可以访问操作系统内核服务。它类似于 DOS 下的 command 和后来的 cmd.exe。Shell 既是一种命令语言&#xff0c;又是一种程序设计语言。 2.入门 vim hello.sh 编辑如下内容#!/bin/bas…...

大连网龙建站优化推广/网络舆情监测系统软件

更多代码请见&#xff1a;https://github.com/xubo245 基因数据处理系列 1.解释 重新运行&#xff0c;跟换了文件地址 后来终端&#xff0c;需要运行其他的2.代码&#xff1a; hadoopMaster:~/disk2/xubo/project/alignment/sparkBWA$ vi sparkBWA.sh for j in 10000 10000…...

美国做科普的网站/品牌营销策划方案怎么做

论坛管理点击组件-论坛&#xff0c;即可打开论坛管理系统。首页打开论坛管理系统后首页如下&#xff1a;设置点击设置&#xff0c;会弹出含有系统设置、分区设置、模块设置的页面系统设置点击系统设置后&#xff0c;点击右边列表里任何一行&#xff0c;即可对该行的配置值更改&…...

邢台做网站的价格究竟多少钱?/交换链接案例

1 问题 解决svn: E160028: Commit failed (details follow): svn is out of date问题 2 分析 项目太久未同步了 3 解决问题 更新项目再传一次咯 有其他交流的想法&#xff0c;可以加我创建的Q群&#xff1a;820080257...

泰安网站开发/怎样优化标题关键词

vsftpd简介vsftpd是一款在Linux发行版中最受推崇的FTP服务器程序&#xff1b;特点是小巧轻快&#xff0c;安全易用&#xff1b;能让其自身特点得发挥和掌握&#xff0c;也然最主要的是会用&#xff1b;目前在开源操作系统中常用的FTPD套件主要有ProFTPD、PureFTPd和wuftpd等&am…...