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

数组题型-二分查找-JS

news 来源：原创 2025/8/12 13:44:21

二分查找伪代码

1.定义 target 是在⼀个在左闭右闭的区间⾥，也就是[left, right]

    let left=0;let right=nums.length-1;// 定义target在左闭右闭的区间⾥，[left, right]while(left<=right){// 当left==right，区间[left, right]依然有效，所以⽤ <=let middle=Math.floor((left+right)/ 2); // 防⽌溢出if(nums[middle]===target) return middle;// 数组中找到⽬标值，直接返回下标if (nums[middle]>target){right=middle-1;// target 在左区间，所以[left, middle - 1]}if(nums[middle]<target){left=middle+1;// target 在右区间，所以[middle + 1, right]}}// 未找到⽬标值return -1;

时间复杂度： O(log n)

空间复杂度： O(1)

2.target 是在⼀个在左闭右开的区间⾥，也就是[left, right)

其实就是right取值的时候取不到。

    let left=0;let right=nums.length-1;// 定义target在左闭右开的区间⾥，[left, right)while(left<right){// 当left==right，区间[left, right)无效效，所以⽤ <let middle=Math.floor((left+right)/ 2); // 防⽌溢出if(nums[middle]===target) return middle;// 数组中找到⽬标值，直接返回下标if (nums[middle]>target){right=middle;// target 在左区间，所以[left, middle）}if(nums[middle]<target){left=middle+1;// target 在右区间，所以[middle + 1, right）}}// 未找到⽬标值return -1;

leetcode相关题目

704.二分查找

35. 搜索插⼊位置

34. 在排序数组中查找元素的第⼀个和最后⼀个位置

69.x 的平⽅根

367. 有效的完全平⽅数

小技巧：在循环结束时，left 和 right 的值已经交叉，left 指向第一个大于目标值的位置，right 指向最后一个小于目标值的位置。

704.二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：

你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

就是二分法基础背熟没什么好说的

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var search = function(nums, target) {let left=0;let right=nums.length-1;while(left<=right){let middle=Math.floor((left+right)/ 2);if(nums[middle]===target) return middle;if (nums[middle]>target){right=middle-1;}if(nums[middle]<target){left=middle+1;}}return -1;
};

35.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为 无重复元素 的升序排列数组
-104 <= target <= 104

直接一部分是二分法查值，另一部分就是我们说的技巧在循环结束时，left 和 right 的值已经交叉，left 指向第一个大于目标值的位置，right 指向最后一个小于目标值的位置。

我们要把元素放在合适的位置，我们找到的值不存在于数组中，也就是说最终的left和right是距离目标最接近的位置。但left指向的是第一个大于目标值的位置，因此把元素放入left现在的位置就可以。

/*** @param {number[]} nums* @param {number} target* @return {number}*/
var searchInsert = function(nums, target) {let left=0;let right=nums.length-1;while(left<=right){let middle=Math.floor((left+right)/2)if(nums[middle]===target) return middle;if(target>nums[middle]) left=middle+1;if(target<nums[middle]) right=middle-1;}return left;
};

34.在排序数组中查找元素的第⼀个和最后⼀个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

我们可以通过二分查找找到一个元素的位置，以此为起点，向两边查找相等的元素即可。

/*** @param {number[]} nums* @param {number} target* @return {number[]}*/
var searchRange = function(nums, target) {let left = 0;let right = nums.length - 1;while (left <= right) {let middle = Math.floor((left + right) / 2);if (nums[middle] === target) {// 找到目标值，查找起始和结束位置let start = middle;let end = middle;// 向左查找起始位置while (start > 0 && nums[start - 1] === target) {start--;}// 向右查找结束位置while (end < nums.length - 1 && nums[end + 1] === target) {end++;}return [start, end];} else if (nums[middle] < target) {left = middle + 1; // 目标值在右半部分} else {right = middle - 1; // 目标值在左半部分}}return [-1,-1]};

69.x 的平⽅根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：
输入：x = 4
输出：2
示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
提示：

0 <= x <= 231 - 1

也是二分查找，注意我们的技巧，在循环结束时，left 和 right 的值已经交叉，left 指向第一个大于目标值的位置，right 指向最后一个小于目标值的位置。因此这里应该是right right是最接近目标值又小于目标值的。

/*** @param {number} x* @return {number}*/
var mySqrt = function(x) {let left=0;let right=x;while(left<=right){let middle=Math.floor((left+right)/2)if(middle*middle===x) return middleif(middle*middle>x) right=middle-1;if(middle*middle<x) left=middle+1;}return right
};

367.有效的完全平⽅数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如 sqrt 。

示例 1：
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。
示例 2：
输入：num = 14
输出：false
解释：返回 false ，因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。
提示：

1 <= num <= 231 - 1

这个和上题类似但是更加简单只要对数进行二分判断如果输的平方可以和它相等那就是找到了；否则当left和right相交时，就是不存在。

/*** @param {number} x* @return {boolean}*/
var isPerfectSquare = function(x) {let left=0;let right=x;while(left<=right){let middle=Math.floor((left+right)/2)if(middle*middle===x) return trueif(middle*middle>x) right=middle-1;if(middle*middle<x) left=middle+1;}return false
};

数组题型-二分查找-JS

二分查找伪代码 1.定义 target 是在⼀个在左闭右闭的区间⾥，也就是[left, right] let left0;let rightnums.length-1;// 定义target在左闭右闭的区间⾥，[left, right]while(left<right){// 当leftright，区间[left, right]依然有效&#x…...

编程日记 2025/8/12 13:44:21

STL——vector

目录 1 vector介绍 2 vector使用 2.1 vector的定义 2.1.1 无参构造 2.1.2 构造并初始化N个Val 2.1.3 拷贝构造 2.1.4 使用迭代器初始化构造 2.1.5 使用大括号初始化构造 2.2 vector的迭代器 2.2.1 const 迭代器 2.3 vector的空间增长 2.4 vector的增删改查 2.5 ve…...

编程日记 2025/8/6 23:21:52

国内首款载重1吨级无人运输机TP1000首飞成功 2026年投入应急救援

大湾区经济网珠海快讯，据央视新闻报道，3月15日上午，国内首款载重1吨级大型无人运输机TP1000在山东成功首飞。该机由中国民航适航标准完全自主研发，起飞重量3.3吨，满载航程达1000公里，具备智能空投功能&…...

编程日记 2025/7/30 17:10:54

python-leetcode 54.全排列

题目： 给定不含重复数字的数组nums,返回其所有可能的全排列，可以按任意顺序返回答案回溯法一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通…...

编程日记 2025/8/9 8:11:33

人工智能实现电脑任务自动化的开源软件

人工智能实现电脑任务自动化的开源软件 hallo大家好，我是星哥，今天给大家介绍一个开源软件，融合了人工智能与机器人流程自动化（AIRPA）的开源软件autoMate! autoMate是什么 autoMate 是一款由开源开发的本地自动化工…...

编程日记 2025/8/10 1:16:28

串口烧录出现频繁回复乱码频繁回复一个数字且烧录失败字节混乱

这是因为你的芯片没有处于系统存储区启动一直未进入bootloader 解决办法是检查boot引脚接正确没，要在系统存储器启动...

编程日记 2025/7/24 4:15:03

ens33没有分配到IPV4问题

方法一：手动为 ens33 接口分配 IP 地址你能够借助 ip 命令手动给 ens33 接口分配 IP 地址。不过这种方式在系统重启之后就会失效。步骤查看网络信息先查看一下当前网络的子网信息，例如网关地址和子网掩码等，你可以通过路由器管理界面或…...

编程日记 2025/8/10 1:50:02

搭建主从服务器

任务需求客户端通过访问 www.nihao.com 后，能够通过 dns 域名解析，访问到 nginx 服务中由 nfs 共享的首页文件，内容为：Very good, you have successfully set up the system. 各个主机能够实现时间同步，并且都开启防…...

编程日记 2025/8/6 7:57:35

【实测闭坑】LazyGraphRAG利用本地ollama提供Embedding model服务和火山引擎的deepseek API构建本地知识库

LazyGraphRAG 2024年4月，为解决传统RAG在全局性的查询总结任务上表现不佳，微软多部门联合提出Project GraphRAG（大模型驱动的KG）；2024年7月，微软正式开源GraphRAG项目，引起极大关注&#xff0c…...

编程日记 2025/8/8 13:58:24

[Lc14_priority_queue] 最后一块石头重量 | 数据流中的第 K 大元素 | 前K个高频单词 | 数据流的中位数

目录 1.最后一块石头的重量题解 2.数据流中的第 K 大元素题解 3.前K个高频单词题解代码 ⭕4.数据流的中位数题解在C中，使用标准库中的priority_queue，默认情况下它是一个最大堆（即大堆排序），这意味着最…...

编程日记 2025/8/10 13:00:05

Electron使用WebAssembly实现CRC-16 MAXIM校验

Electron使用WebAssembly实现CRC-16 MAXIM校验将C/C语言代码，经由WebAssembly编译为库函数，可以在JS语言环境进行调用。这里介绍在Electron工具环境使用WebAssembly调用CRC-16 MAXIM格式校验的方式。 CRC-16 MAXIM校验函数WebAssembly源文件 C语言实…...

编程日记 2025/8/11 23:56:41

案例5_1:单位数码管显示0

文章目录文章介绍效果图仿真图5_1放置单位数码管代码5_1.c 文章介绍效果图仿真图5_1 复制案例1_2的仿真图，在此基础上修改注意：栅格大小需要缩小放置单位数码管代码5_1.c #include <reg52.h>#define uchar unsigned char #define uint un…...

编程日记 2025/8/5 4:42:11

OpenCV计算摄影学（20）非真实感渲染之增强图像的细节函数detailEnhance()

操作系统：ubuntu22.04 OpenCV版本：OpenCV4.9 IDE:Visual Studio Code 编程语言：C11 算法描述此滤波器增强特定图像的细节。 cv::detailEnhance用于增强图像的细节，通过结合空间域和频率域的处理，提升图像中特定细节…...

编程日记 2025/8/9 18:57:31

linux按照nginx

第一步先按照依赖gcc 一键安装上面四个依赖 Nginx的编译安装需要一些依赖库，如gcc、make、zlib、openssl等。可以使用yum命令安装这些依赖： yum -y install gcc zlib zlib-devel pcre-devel openssl openssl-devel 创建目录 mkdir /usr/nginx 切换…...

编程日记 2025/8/8 16:50:59

SpringMVC（八）Knife4j 接口文档

目录一基础使用 1 配置pom.xml相关依赖 2 项目配置 3 输入指定路径（http://localhost:8080/doc.html） 二一些使用方法 1 Tag 2 Operation 3 Schema 4 Parameter 5 可以根据需求来设置补充：日期的格式化 Knife4j 是基于 Swag…...

编程日记 2025/8/11 23:37:41

Java集成MQTT和Kafka实现稳定、可靠、高性能的物联网消息处理系统

Java集成MQTT和Kafka实现高可用方案 1. 概述在物联网(IoT)和分布式系统中，消息传递的可靠性和高可用性至关重要。本文将详细介绍如何使用Java集成MQTT和Kafka来构建一个高可用的消息处理系统。 MQTT(消息队列遥测传输)是一种轻量级的发布/订阅协议，适用于资源受限的设备和…...

编程日记 2025/8/9 7:10:21

【操作系统安全】任务6：Linux 系统文件与文件系统安全学习指南

目录一、文件系统基础概念二、查看文件系统信息 2.1 磁盘空间查看 2.2 分区与挂载管理 2.3 文件系统类型操作三、文件系统权限配置 3.1 基础权限管理 3.2 所有权管理 3.3 特殊权限设置四、文件操作基础 4.1 文件创建 4.2 文件删除 4.3 文件复制与移动 4.4 文件…...

编程日记 2025/8/11 3:03:47

华为中小型企业项目案例

实验目的（1）熟悉华为交换机和路由器的应用场景（2）掌握华为交换机和路由器的配置方法实验拓扑实验拓扑如图所示。华为中小型企业项目案例拓扑图实验配置市场部和技术部的配置创建VLANLSW1的配置 [LSW1]vlan batch 10 20 [LSW1]q…...

编程日记 2025/8/11 2:50:09

Zabbix安装（保姆级教程）

Zabbix 是一款开源的企业级监控解决方案，能够监控网络的多个参数以及服务器、虚拟机、应用程序、服务、数据库、网站和云的健康状况和完整性。它提供了灵活的通知机制，允许用户为几乎任何事件配置基于电子邮件的告警，从而能够快速响应服务器问题。Zabbix 基于存储的数据提供…...

编程日记 2025/8/9 6:46:40

JDBC数据库连接池技术详解——从传统连接方式到高效连接管理

1. 引言在开发数据库应用时，我们通常需要与数据库建立连接并执行SQL语句。传统的JDBC连接方式虽然简单直接，但在高并发场景下容易带来性能问题，甚至导致系统崩溃。因此，引入数据库连接池（Connection Pool&#xff09…...

编程日记 2025/8/9 10:11:13

微服务存在的问题及解决方案

微服务存在的问题及解决方案 1. 存在问题 1.1 接口拖慢因为一个接口在并发时，正好执行时长又比较长，那么当前这个接口占用过多的 Tomcat 连接，导致其他接口无法即时获取到 Tomcat 连接来完成请求，导致接口拖慢，甚至…...

编程日记 2025/8/8 18:17:51

C语言中的结构体数组

一、什么是结构体数组？在C语言中，**结构体（struct）**是一种自定义数据类型，它可以将不同类型的数据组合成一个单一的数据结构。结构体数组则是多个结构体元素按顺序存储在内存中的集合。通过结构体数组，可以存储多个相同类型的结构体，每个结构体都拥有自己独立的成员变…...

编程日记 2025/8/11 13:25:29

[GESP 202412 一级 T1] 温度转换

描述小杨最近学习了开尔文温度、摄氏温度和华氏温度的转换。令符号 KK 表示开尔文温度，符号 CC 表示摄氏温度，符号 FF 表示华氏温度，这三者的转换公式如下： C K - 273.15 F C*1.8 32 现在小杨想编写一个程序计算某一开尔文…...

编程日记 2025/8/11 2:39:32

虚幻基础：GAS

文章目录 Gameplay Tag：项目类：可直接按标签管理游戏中的各种对象。其他：数据表格：gameplaytag primary data asset：项目类：存储游戏中的数据：通常用于配置表蓝图：primary data asse…...

编程日记 2025/8/11 6:45:19

案例：图书管理

掌握图书管理案例的实现，能够使用Spring Boot整合Thymeleaf完成图书管理案例。 1.任务需求 （1）项目使用Spring Boot整合Thymeleaf，项目展示的页面效果全部通过Thymeleaf的模板文件实现。 （2）查询所有图书。…...

编程日记 2025/8/12 4:37:17

Pycharm 社区版安装教程

找到安装包双击安装文件---点击下一步一般路径是：C:\Rambo\Software\Development 选择完成后就是如下地址： C:\Rambo\Software\Development\PyCharm Community Edition 2024.3.3 点击上述3个位置就可以了----下一步等待安装就可以了---完成后点击完成…...

编程日记 2025/8/11 10:15:59

RabbitMQ 全面详解（附面试重点）

RabbitMQ 全面详解（附面试重点） 一、RabbitMQ 与其他消息队列对比特性RabbitMQKafkaRocketMQActiveMQ设计定位企业级消息中间件（传统业务场景）高吞吐分布式流处理平台（日志、大数据）金融级高可靠消息中间…...

编程日记 2025/8/9 1:28:17

浏览器好用的去广告插件和暗黑模式护眼插件

提升浏览体验：Edge浏览器的Adblock和Dark Mode扩展 Adblock：告别广告干扰功能：高效拦截弹窗、横幅和视频广告，提升网页整洁度，加快加载速度，节省流量。安装链接：安装Adblock Dark Mode for E…...

编程日记 2025/8/12 13:16:42

VBA第二十七期数据录入中验证格式有效性

Excel的数据有效性验证是一个有用的工具，但会需要我们向使用数据单元格提前设定有效性验证规则。这样一来使数据的有效性验证功能不能使用在VBA编程中。下面介绍如何在工作表中使用Change事件来创建数据有效性验证过程。监视单元格区域验证数据输入的有效性&#xf…...

编程日记 2025/8/6 14:08:58

基于 Verilog 的时序设计：从理论到实践的深度探索

在数字电路设计领域，时序设计是一个至关重要的环节，它涉及到组合逻辑电路与时序逻辑电路的设计差异、时钟信号的运用以及触发器的工作原理等多个方面。本文将围绕基于 Verilog 的时序设计实验展开，详细阐述实验过程、代码实现以及结果分析，帮助读者深入理解时序设计的核心概…...

编程日记 2025/8/4 12:54:33

[JAVASE] 反射

一. 反射概念反射（Reflection）允许程序在运行时查询、访问和修改类、接口、字段和方法的信息。反射提供了一种动态操作类的能力。二. Java反射的基本使用和应用 java.lang.reflect 是 Java 反射机制的核心包 ，提供了操作类及其成员&…...

编程日记 2025/8/5 4:43:41

C++11智能指针简述

一、实现原理在智能指针对象中有一个裸指针，此指针存储的是动态创建对象的地址，用于生存期控制，能够确保智能指针对象离开所在作用域时，自动正确地销毁动态创建的对象，防止内存泄漏。使用裸指针存在的问题&#xff…...

编程日记 2025/8/4 4:31:50

导入hutool依赖 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.8.36</version>获取验证码接口 Autowiredprivate Captcha captcha;private final static Long VALIDA…...

编程日记 2025/8/3 14:30:43

QT中读取QSetting文件

1.ini文件的格式头文件 #include <QSettings> #include <QStringList> #include <QtCore> #include <QDebug>2.读文件 //ini文件的读取 void iniTest::readIniFile(QString filePath) {//1.打开ini文件QSettings m_iniFile(filePath, QSettings::I…...

编程日记 2025/8/8 12:58:33

网络安全 --- 基于网络安全的 Linux 最敏感目录及文件利用指南

目录基于网络安全的 Linux 最敏感目录及文件利用指南 Linux 中最敏感的目录及文件 1. /etc 2. /root 3. /var/log 4. /proc 5. /tmp 6. /home 7. /boot 8. /dev 如何利用这些敏感文件你可能没想到的知识点总结 Linux 中最敏感的目录及文件 1. /etc 存放内容&a…...

编程日记 2025/8/8 11:05:12

操作系统八股文整理(一)

操作系统八股文整理一、进程和线程的区别二、进程与线程的切换过程一、进程切换进程切换的步骤： 二、线程切换线程切换的步骤： 三、进程切换与线程切换的对比四、上下文切换的优化三、系统调用一、系统调用的触发二、从用户空间切换到内核空间三、执行…...

编程日记 2025/8/9 1:43:44

ssh转发笔记

工作中又学到了，大脑转不过来现有主机A，主机B，主机C A能访问B，B能访问C，A不能访问C C上80端口有个服务，现在A想访问这个服务，领导让用ssh转发，研究半天没找到理想的语句&#xf…...

编程日记 2025/8/7 8:14:52

[从零开始学SSM] Bean的配置

bean基础配置 bean别名配置 bean的作用范围配置由运行结果可知，Spring创建的bean默认是单例的那么如果我想创建非单例的bean怎么办，这时候就需要用到配置的方式完成了：在<bean>的属性中添加一个scope属性，该属性默认是si…...

编程日记 2025/8/12 1:21:55

CML（Current Mode Logic）电平详解

一、CML的定义与核心特性 CML（Current Mode Logic，电流模式逻辑） 是一种基于电流驱动的高速差分信号标准，专为 10Gbps以上超高速传输设计。其核心原理是通过恒定的尾电流源切换电流路径，生成低摆幅差分信号&#x…...

编程日记 2025/8/4 15:26:26

【链表世界的深度探索：从基础到高阶的算法解读】—— LeetCode

文章目录反转链表链表的中间结点合并两个有序链表相交链表两数相加两两交换链表中的节点重排链表合并K个升序链表K个一组翻转链表反转链表这道题目的意思很好理解，即将链表给反转即可方法一： 利用双指针进行操作，定义两个变量 prev 以及…...

编程日记 2025/8/12 4:22:30

JMeter 性能测试

Jmeter 用户手册名词解释： RPS：每秒请求数-每秒向服务器发送多少请求数（一个场景，系统面临多大的压力） TPS：每秒事务数-每秒能够处理多少请求/事务数性能评价标准（其中的一个核心指标&#x…...

编程日记 2025/8/11 6:11:22

LCR 159. 库存管理 III

这道题虽然简单，但是可以有多种解法，适合练习各种解法。可以用基于快速排序思想的快速选择算法： class Solution { public:vector<int> inventoryManagement(vector<int>& stock, int cnt) {vector<int> res;int le…...

编程日记 2025/8/9 8:29:52

Spring IOC(五个类注解)

controller、service、Repository、Component 、Configurationpackage com.java.ioc;import com.java.ioc.Controller.HelloController; import com.java.ioc.rep.UserRepository; import com.java.ioc.service.UserService; import org.springframework.boot.SpringApplicatio…...

编程日记 2025/7/31 10:58:20

相关文章：