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

LeetCode_Python_二分查找算法

二分查找

  • 算法要求
  • 二分查找过程
  • 如何更新左右边界
  • 实例
    • type1:常规记录中间元素
    • type2:取跳出循环后的左或右边界

算法要求

  1. 顺序存储结构
  2. 元素大小有序

二分查找过程

  1. 将元素排序;
  2. 将中间位置记录的这个元素与目标元素比较;
    2.1 如果相同,则查找成功;
    2.2 否则将元素分为前、后两部分,如果目标元素相比查找元素在左,则更新右边界;如果目标元素相比查找元素在右,则更新左边界;
    2.3 重复步骤2

如何更新左右边界

  1. 查找区间为 [left, right],循环条件为 left <= right;左右分别更新为 mid+1、mid-1
  2. 查找区间为 [left, right),循环条件为 left < right;左右分别更新为 mid+1、mid

实例

type1:常规记录中间元素

  1. 有效的平方数
def isPerfectSquare(num):left,right=0,numwhile left<=right:mid=(left+right)//2if mid*mid==num:return Trueelif mid*mid<num:left=mid+1else:right=mid-1return False

type2:取跳出循环后的左或右边界

  1. 找出X的平方根

:跳出循环时左右边界的意义,更新前的左右边界分别满足 if 后的条件

def findSqrt(x):left,right=0,xwhile left<=right:mid=(left+right)//2if mid*mid<=x:left=mid+1else:right=mid-1#跳出循环时 left>right,说明上一个更新的是 left,即(left-1)*(left-1)<=x;又 right*right>x,所以left*left>x,因此 left-1 就是要查找的目标数return left-1  
  1. 搜索插入位置
    给定一个排序数组nums和一个目标值target,返回目标值索引。如果不存在,返回它将会被按顺序插入的位置。
def searchInsert(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-1#跳出循环时后,nums[left-1]<target & nums[right]>target i.e nums[left]>target,因此target要放在left位置return left  

相关文章:

LeetCode_Python_二分查找算法

二分查找算法要求二分查找过程如何更新左右边界实例type1&#xff1a;常规记录中间元素type2&#xff1a;取跳出循环后的左或右边界算法要求 顺序存储结构元素大小有序 二分查找过程 将元素排序&#xff1b;将中间位置记录的这个元素与目标元素比较&#xff1b; 2.1 如果相同&a…...

功能测试三年,是时候做出改变了

前言 测试行业3年多经验&#xff0c;学历大专自考本科&#xff0c;主要测试方向web&#xff0c;PC端&#xff0c;wap站&#xff0c;小程序公众号都测试过&#xff0c;app也测过一些&#xff0c;C端B端都有&#xff0c;除功能外&#xff0c;接口性能也有涉猎&#xff0c;但是不…...

图扑孪生工厂流水线组态图可视化

前言 2018 年&#xff0c;世界经济论坛(WEF)携手麦肯锡公司共同倡议并正式启动了全球“灯塔工厂网络项目”(Lighthouse Network)&#xff0c;共同遴选率先应用工业革命 4.0 技术实现企业盈利和持续发展的创新者与示范者。这就使得工厂系统需要对各流水线及生产运行成本方面进行…...

车机开发—【CarService启动流程】

汽车架构&#xff1a;车载HAL是汽车与车辆网络服务之间的接口定义&#xff08;同时保护传入的数据&#xff09;&#xff1a; 车载HAL与Android Automotive架构&#xff1a; Car App&#xff1a;包括OEM和第三方开发的AppCar API&#xff1a;内有包含CarSensorManager在内的AP…...

webpack中require.context的运用

1. 作用&#xff1a; 利用require创建context (上下文)&#xff0c;来告知在编译时具体需要导入哪些模块(即&#xff1a;批量处理待导入模块进行导入)&#xff1b; webpack会在构建的时候解析代码中的require.context() (实际上是webpack的方法&#xff0c;vue一般基于webpack…...

2023“Java基础-中级-高级”面试集结,已奉上我的膝盖

Java基础&#xff08;对象线程字符接口变量异常方法&#xff09; 面向对象和面向过程的区别&#xff1f; Java 语言有哪些特点&#xff1f; 关于 JVM JDK 和 JRE 最详细通俗的解答 Oracle JDK 和 OpenJDK 的对比 Java 和 C的区别&#xff1f; 什么是 Java 程序的主类&…...

RabbitMQ之发布确认

发布确认 1 发布确认原理 生产者将信道设置成 confirm 模式,一旦信道进入 confirm 模式,所有在该信道上面发布的消息都将会被指派一个唯一的 ID(从 1 开始),一旦消息被投递到所有匹配的队列之后,broker就会发送一个确认给生产者(包含消息的唯一 ID),这就使得生产者知道消…...

一文读懂函数编程及其工作原理

微软MVP实验室研究员 马洪喜-微软 MVP 19年研发经验 云计算咨询顾问专家 容器云及基础架构云技术专家 DevOps 及微服务咨询专家 什么是函数编程 我先用通俗的大白话给大家解释一下函数(Functions, Function as a Service, FaaS)的几个要点&#xff0c;这样看后面示例时才不…...

WSO2 apim Subscribe to an API

WSO2 apim Application Subscribe to an API1. Published an Api2. Subscribe to an API using Key Generation Wizard3. Subscribe to an existing application4. AwakeningWSO2安装使用的全过程详解: https://blog.csdn.net/weixin_43916074/article/details/127987099. Offi…...

聚类(性能度量)

文章目录聚类&#xff08;性能度量&#xff09;外部指标例1内部指标例2聚类&#xff08;性能度量&#xff09; 对数据集 D{x1,x2,...,xm}D\{x_1,x_2,...,x_m\}D{x1​,x2​,...,xm​} &#xff0c;假定通过聚类给出的簇划分为 C{C1,C2,...,Ck}C\{C_1,C_2,...,C_k\}C{C1​,C2​,…...

GPT-4——比GPT-3强100倍

GPT-4——比GPT-3强100倍 当前世界上最强大的人工智能系统当属ChatGPT。推出2个月用户数就突破1亿。ChatGPT是当下最炙手可热的话题&#xff0c;科技圈几乎人人都在讨论。这边ChatGPT的热度还在不断攀升&#xff0c;另一边来自《纽约时报》的最新报道称ChatGPT即将被自家超越&…...

echart中x轴数据过多时展示不全

项目中遇到需要展示一些柱状图&#xff0c;之前做相关功能时&#xff0c;横坐标x轴一直用的是时间&#xff0c;所以没有注意到这个问题。 如下图所示&#xff1a; 当x轴显示的是”人名“这种类型的值的时候&#xff0c;这种显示情况就有问题了&#xff0c;这样就不会知道&…...

关于GIS原理的实际分析应用题的一些解法

话不多说&#xff0c;看题.01 公园选址问题1题目请写出利用GIS技术进行公园选址的空间操作步骤。其中公园选址条件:1&#xff09;为了安静舒适&#xff0c;要求该园区离主要公路1公里以外&#xff0c;且交通方便&#xff0c;离主要公路3公里以内。2&#xff09;公园最好依附在大…...

混合精度训练,FP16加速训练,降低内存消耗

计算机中的浮点数表示&#xff0c;按照IEEE754可以分为三种&#xff0c;分别是半精度浮点数、单精度浮点数和双精度浮点数。三种格式的浮点数因占用的存储位数不同&#xff0c;能够表示的数据精度也不同。 Signed bit用于控制浮点数的正负&#xff0c;0表示正数&#xff0c;1表…...

每天五分钟机器学习:新的大规模的机器学习机制——在线学习机制

本文重点 本节课程我们将学习一种新的大规模的机器学习机制--在线学习机制。在线学习机制让我们可以模型化问题。在线学习算法指的是对数据流进行学习而非离线的静态数据集的学习。许多在线网站都有持续不断的用户流,对于每一个用户,网站希望能在不将数据存储到数据库中便顺…...

计算机组成原理错题

静态RAM&#xff08;SRAM&#xff09;和动态RAM&#xff08;DRAM&#xff09;的基本电路图不同&#xff0c;因此可以通过观察存储器的基本电路图来判断它属于哪一类。 静态RAM的基本电路图包括一个存储单元和一个数据选择器。每个存储单元由一个触发器&#xff08;flip-flop&a…...

数学基础整理

收纳一些天天忘的结论qwq 线性求逆元 invi(p−pi)invpmodiinv_i(p-\dfrac{p}{i})\times inv_{p\bmod i}invi​(p−ip​)invpmodi​ 卡特兰数 组合数公式&#xff1a;HnC2nn−C2nn−1H_nC_{2n}^n-C_{2n}^{n-1}Hn​C2nn​−C2nn−1​ 递推式&#xff1a;HnHn−1(4n−2)n1H_n\d…...

JavaWeb11-死锁

目录 1.死锁定义 1.1.代码演示 1.2.使用jconsole/jvisualvm/jmc查看死锁 ①使用jconsole&#xff1a;最简单。 ②使用jvisualvm&#xff1a;&#xff08;Java虚拟机&#xff09;更方便&#xff0c;更直观&#xff0c;更智能&#xff0c;更高级&#xff0c;是合适的选择。 …...

堆的概念和结构以及堆排序

前言 普通的二叉树是不适合用数组来存储的&#xff0c;因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储&#xff0c;需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事&#xff0c…...

【Linux学习笔记】1.Linux 简介及安装

前言 本章介绍Linux及其安装方法。 Linux 简介 Linux 内核最初只是由芬兰人林纳斯托瓦兹&#xff08;Linus Torvalds&#xff09;在赫尔辛基大学上学时出于个人爱好而编写的。 Linux 是一套免费使用和自由传播的类 Unix 操作系统&#xff0c;是一个基于 POSIX 和 UNIX 的多…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...