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

【优选算法二分查找】二分查找算法入门详解：二分查找小专题

news 来源：原创 2025/7/15 12:29:01

x 的平方根

题目解析

算法原理

解法一：暴力解法

如果要求一个数(x)的平方根，可以从 0 往后枚举，直到有一个数(a)，a^2<=x，(a+1)^2>x，a即为所求；

解法二：二分查找

分析二段性

因为暴力枚举的数字从1开始递增，所以枚举的数是有序的，并且能以 a 为边界点，把枚举的数组分成两个部分：

因为这道题分 a^2<=x，a^2>x 两种情况，而不是分成三种情况，所以使用不朴素的二分查找；

left 初始化为1，right 的初始化需要商榷，所以以 mid 的值对应的 a^2 和 x 的大小关系进行讨论：

1. a^2 <= x

2. a^2 > x

处理细节问题

根据范围，我们可以发现 x 是可以小于1的，如果当 x=0.5之类的小数，那么开根号得到的数的整数部分一定是0，所以当 x<1，直接返回0即可；所以 left 初始化为1

编写代码

搜索插入位置

题目解析

算法原理

解法：二分查找

查找二段性

通过下面的例子可以发现，插入的位置要么是第一个大于 target 的数的下标，要么是 target 大于数组中所有元素，而被插入到末尾：

所以插入 target 的位置特点是第一个大于等于 target 的元素下标，这个下标即为返回值，所以有如下二段性：

left 和 right 的更新策略

分析 mid 落在上面两个区间时，left 和 right 的更新策略：

1.mid >= target

2.mid < target

编写代码

山脉数组的峰顶索引

题目解析

算法原理

如果要找峰顶元素的下标，那么第一个元素和最后一个元素其实是不需要考虑的；

解法一：暴力枚举

定义一个指针，从起始位置开始往后扫描，当扫描到一个元素的值大于后面一个元素的值，就返回这个元素的下标，时间复杂度为O(N);

解法二：二分查找

分析二段性

我们发现，哪怕这个数组并不是有序的，依旧可以使用二分查找，就是因为数组具有二段性；

left 和 right 的更新策略

分析 mid 落在上面两个区间时，left 和 right 的更新策略：

1. arr[mid] > arr[mid-1]

2. arr[mid] < arr[mid-1]

编写代码

寻找峰值

题目解析

算法原理

如果起始位置是呈现下降趋势的，就直接返回起始位置下标0即可，因为nums[-1]为负无穷；

如果刚开始往后遍历，一直是上升，直到峰值后下降，返回峰值下标：

当遍历完所有数组，都是呈上升趋势，返回最后一个元素下标即可，因为nums[length]为无穷小

解法一：暴力枚举

定义一个指针直接往后扫描，根据上面的三种情况作出相应的处理即可；时间复杂度是考虑最坏的情况，如第三种情况，所以为O(N)

解法二：优化暴力解法，二分查找

分析二段性

我们分析数组任意区间相邻两个点的情况：

1. nums[i] > nums[i+1] ，在[0,i] 区间一定存在至少一个峰值，接下来可以去 [0,i] 区间找：

2. nums[i] < nums[i+1]，在 [i+1,length-1] 区间至少存在一个峰值，所以可以去这个区间找：

所以根据 nums[i] 与 nums[i+1] 的关系，把数组分成了两部分，去其中一个部分查找结果；

刚刚在山峰数组中找索引，还算不上严格的无序；这道题是严格的无序，但是依旧能使用二分查找解决，说明二段性是决定一个题能否使用二分查找的必要条件；

left 和 right 的更新策略

根据 arr[mid] 和 arr[mid+1] 的关系，更新left 和right;

1. arr[mid] > arr[mid+1] ，在[0,mid] 区间一定存在至少一个峰值：

2. arr[mid] < arr[mid+1]，在 [i+1,length-1] 区间至少存在一个峰值：

编写代码

暴力枚举

二分查找

寻找旋转排序数组中的最小值

题目描述

算法原理

经过旋转的数组有什么特性呢？

因为数组元素是互不相同的，所以折线图又可以分成两部分：

左边部分严格在nums的分界线上面，右边部分严格在nums分界线下面，并且两个折线部分都是递增的；

解法一：暴力枚举

从前往后扫描数组，直到找到最小值；时间复杂度O(N)；暴力解法慢就慢在没有利用旋转数组能分成两个递增折线，且左边严格高于右边的特性；

解法二：二分查找

分析二段性

如果把问题抽象成折现图，那么就会发现这个数组有明显的二段性，数组的两个部分被分界线严格划分；对于AC，nums[i] > nums[length-1]；对于DE，nums<=nums[length-1];

注意：本题的特殊之处，是拿中间元素的值和末尾元素的值的大小关系，来分成两个区间

所以要找最小值，我们只需要找到下标分割线所在的位置，即是最小值下标位置，所以就是查找右边区域的左端点；

left 和 right 的更新策略

分析 mid 落在上面两个区间时，left 和 right 的更新策略：

注意，这个数组是经过有序递增数组旋转得到的数组，这就避免了很多边界情况的讨论，旋转数组的值分布一定是分成两个递增折线，并且左边折线严格都大于右边；

1. AC：nums[mid] > nums[length-1]

2. DF：nums[mid] <= nums[length-1]

上面是以末尾元素为参照物，我们可以选起始元素为参照点吗？

我们发现，AC区间是严格大于nums[0] 的，CD区间也是严格小于 nums[0] 的，也具有二段性；

编写代码

0~n-1中缺失的数字

题目描述

算法原理

解法一：哈希表

如果是n个数字，就建 n+1个桶的哈希表，遍历原始数组并且填入哈希表，最后找出 val=0 的key即可；时间复杂度为 O(N)，但是还要利用O(N)的空间复杂度

解法二：直接遍历

从前往后直接遍历，时间复杂度为 O(N)；

解法三：位运算

异或 ^ ，把缺失元素的数组，和完整数组的每一个元素进行异或操作：

异或有一个特性，就是相同元素相互抵消，最终异或结果就是缺失的数；

时间复杂度为 O(N)

解法四：数学方法（高斯 / 等差数列求和公式）

因为数组是一个等差升序数组，就是一个等差数列，把完整的数组通过等差数列求和公式求出，再依次减去缺失数字的数组，即可得到缺失的元素；时间复杂度为 O(N)

解法五：二分查找

分析二段性

我们把缺失元素的数组下标标注出来，帮助我们发现二段性：

此时，我们发现，数组可以分成两个区域，下标和元素一一对应是一个区域，不是一一对应，则是类外一个区域，因此，这个数组就有二段性；

left 和 right 的更新策略

如果下标和元素对应，left=mid+1，不能对应则 right = mid；

编写代码

可以把两种特殊的情况合并成一种：

【优选算法二分查找】二分查找算法入门详解：二分查找小专题

x 的平方根题目解析算法原理解法一： 暴力解法如果要求一个数(x)的平方根，可以从 0 往后枚举，直到有一个数(a)，a^2<x，(a1)^2>x，a即为所求； 解法二：二分查找 …...

编程日记 2025/7/15 12:29:01

LeetCode—56. 合并区间（中等）

题目描述： 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。示例1： 输入&#x…...

编程日记 2025/7/14 16:47:33

SHELL----正则表达式

一、文本搜索工具——grep grep -参数条件文件名其中参数有以下： -i 忽略大小写 -c 统计匹配的行数 -v 取反，不显示匹配的行 -w 匹配单词 -E 等价于 egrep ，即启用扩展正则表达式 -n 显示行号 -rl 将指定目录内的文件打…...

编程日记 2025/7/15 11:06:58

web斗地主游戏实现指北

前后端通信作为一个即时多人游戏，不论是即时聊天还是更新玩家状态，都需要服务端有主动推送功能，或者客户端轮询。轮询的时间间隔可能导致游玩体验差，因为不即时更新，而且请求数量太多可能会打崩服务器。建议在cs间…...

编程日记 2025/7/13 23:10:58

ES(elasticsearch)整合Spring boot使用实例

1.1通过docker安装es详细教程参考 docker部署elasticsearch(内涵集群部署的compose文件)-CSDN博客 2.1创建MySQL数据库，通过sql命令进行表的创建与数据的写入（sql命令如下） /*Navicat Premium Data TransferSource Server : localSo…...

编程日记 2025/7/14 15:40:13

创建简单的 PL/pgSQL 存储过程

文章目录创建简单的 PL/pgSQL 存储过程CREATE OR REPLACE FUNCTIONadd_two_numbers(a integer, b integer)RETURNS integerAS$$ ... $$函数体LANGUAGE plpgsql 创建带有 IN 和 OUT 参数的存储过程创建修改数据的存储过程创建带有异常处理的复杂存储过程在 PostgreSQL 中&…...

编程日记 2025/7/15 8:38:45

前端路径“@/“的使用和配置

环境：vitets 需要安装types/node npm install types/node --save-dev在tsconfig.json中添加如果有tsconfig.app.json和tsconfig.node.json文件，则在app.json中添加 "compilerOptions": {"baseUrl":".","paths&q…...

编程日记 2025/7/15 12:10:24

彻底理解ThreadLocal的应用场景和底层实现

一.概念定义： ThreadLocal 是 Java 中所提供的线程本地存储机制，可以利用该机制将数据缓存在某个线程内部，该线程可以在任意时刻、任意方法中获取缓存的数据。其实是可以通过调用 Set() 方法往里面存入值，存入的值是每个线程互…...

编程日记 2025/7/15 12:26:17

机器学习（5）无监督模型之降维PCA算法

主成分分析（Principal Component Analysis, PCA） 是一种经典的无监督学习算法，主要用于数据降维、特征提取和数据可视化。它通过线性变换将数据从原始空间映射到一个新的空间，使得数据的方差最大化，从而实现降维。PCA …...

编程日记 2025/7/15 12:14:03

React 组件中 State 的定义、使用及正确更新方式

🌈个人主页：前端青山 🔥系列专栏：React篇 🔖人终将被年少不可得之物困其一生依旧青山,本期给大家带来React篇专栏内容React 组件中 State 的定义、使用及正确更新方式前言在 React 应用开发中，state …...

编程日记 2025/7/15 11:07:06

18 设计模式之迭代器模式（书籍遍历案例）

一、什么是迭代器模式迭代器模式（Iterator Pattern）是一种行为型设计模式，允许客户端通过统一的接口顺序访问一个集合对象中的元素，而无需暴露集合对象的内部实现。这个模式主要用于访问聚合对象（如集合、数组等&…...

编程日记 2025/7/14 8:54:26

一、Springboot3简介: https://docs.spring.io/spring-boot/docs/current/reference/html/getting-started.html?spmwolai.workspace.0.0.68b62306Q6jtTw#getting-started.introducing-spring-boot 无论使用XML、注解、Java配置类还是他们的混合用法，配置文件过于…...

编程日记 2025/7/15 11:31:23

【Leetcode Top 100】23. 合并 K 个升序链表

问题背景给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。数据约束 k l i s t s . l e n g t h k lists.length klists.length 0 ≤ k ≤ 1 0 4 0 \le k \le 10^4 0≤k≤104 0 ≤ l i s t s […...

编程日记 2025/7/15 11:59:40

显存和GPU之间的通信；GPUDirect P2P，NVLink，NCCL；聚合通信和点对点通信

目录显存和GPU之间的分配显存和GPU之间的通信原语是什么，简单举例说明 GPUDirect P2P，NVLink，NCCL的全称及解释聚合通信和点对点通信聚合通信（Collective Communication）点对点通信（Point-to-Point Communication）为什么使用GPUDirect P2P，NVLink，NCCL…...

编程日记 2025/7/15 12:22:17

2412d,d的7月会议

原文总结卡斯滕 Carsten说,Decard一直在大量试验WebAssembly.他们一直在把d运行时挖出来,直到它工作.他们在浏览器中运行了一些库函数,并试了不同虚机. 他们在移动方面遇见了很多问题,因为不同芯片按不同方式工作.他们想让他们的整个SDK在WASM上运行,但可能需要一年时间才…...

编程日记 2025/7/15 12:12:28

vue框架

以下是一个简单的基于Vue框架的日历组件示例： <template><div class"calendar"><div class"header"><button click"prevMonth"><</button><h2>{{ currentMonth }}</h2><button cli…...

编程日记 2025/7/15 12:09:28

Django drf基于APIView 快速使用

1. 注册 # settings.pyINSTALLED_APPS [,rest_framework, ]2. 路由 from django.urls import pathurlpatterns [path(task/, views.TaskAPIView.as_view()) ]3. 视图 from rest_framework.views import APIView from rest_framework.response import Responseclass TaskAPIV…...

编程日记 2025/7/15 12:13:18

git commit -m “Add user login feature“

当然，这条命令是 Git 中用来提交更改的基本命令，其中包含了一些注释来解释命令的各个部分。下面是对这条命令的详细解释： git commit -m "-m指的是message，git要求每次提交都需要写一下日志"git commit： 这…...

编程日记 2025/7/15 11:42:17

mac: docker : Command not found解决

描述: 安装docker但是docker命令显示Command not found 分析: mac没有配置对应的环境变量解决方案: 打开配置文件: vim ~/.zshrc写docker环境变量: export PATH"/Applications/Docker.app/Contents/Resources/bin:$PATH"保存退出: esc,输入wq,按enter 配置文…...

编程日记 2025/7/15 12:01:48

深入解析 HTML Input 元素：构建交互性表单的核心

🤍 前端开发工程师、技术日更博主、已过CET6 🍨 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 🕠 牛客高级专题作者、打造专栏《前端面试必备》、《2024面试高频手撕题》 🍚 蓝桥云课签约作者、上架课程《Vue.js 和 E…...

编程日记 2025/7/15 12:27:16

Docker--Docker Registry(镜像仓库）

什么是Docker Registry？ 镜像仓库（Docker Registry）是Docker生态系统中用于存储、管理和分发Docker镜像的关键组件。镜像仓库主要负责存储Docker镜像，这些镜像包含了应用程序及其相关的依赖项和配置，是构建和运行Doc…...

编程日记 2025/7/15 11:53:33

Linux 统信UOS 设置程序“桌面快捷方式”与“开机自启动”

最近在统信uos系统 arm64架构上进行QT程序的开发，基本开发完毕后，开始着手准备程序的开机自启动模块，因为一般来说，程序在客户现场使用都是需要开机自启的。然后在百度海淘，很少有这类相关的博客介绍，有一…...

编程日记 2025/7/15 1:17:27

React开发高级篇 - React Hooks以及自定义Hooks实现思路

Hooks介绍 Hooks是react16.8以后新增的钩子API； 目的：增加代码的可复用性，逻辑性，弥补无状态组件没有生命周期，没有数据管理状态state的缺陷。为什么要使用Hooks？ 开发友好，可扩展性强&#…...

编程日记 2025/7/15 11:47:52

shell条件测试

一.命令执行结果判定 && 在命令执行后如果没有任何报错时会执行符号后面的动作 || 在命令执行后如果命令有报错会执行符号后的动作示例： [rootqingdeng shell3]# sh sl.sh /mnt/file is not exist no二.条件判断方法在 shell 程序中，用户可…...

编程日记 2025/7/15 11:59:39

嵌入式蓝桥杯学习5 定时中断实现按键

Cubemx配置打开cubemx。前面的配置与前文一样，这里主要配置基本定时器的定时功能。 1.在Timer中点击TIM6，勾选activated。配置Parameter Settings中的预分频器（PSC）和计数器（auto-reload Register） 补…...

编程日记 2025/7/15 11:07:09

Linux下进程地址空间

文章目录 1. 进程地址空间分布2. 为什么要有进程地址空间一、主要功能二、重要特性三、应用场景四、与TLB的交互 3. 进程具有独立性以x86(32位)为例子 1. 进程地址空间分布进程地址空间，本质是一个描述进程可视范围的大小。地址空间本质是一个内核数据结构,类似…...

编程日记 2025/7/12 16:12:33

基于SpringBoot的养老院管理系统的设计与实现

一、前言随着人口老龄化的加剧，养老院作为老年人养老的重要场所，其管理的高效性和科学性显得尤为重要。传统的养老院管理方式多依赖人工操作，存在信息记录不及时、不准确，管理流程繁琐，资源调配困难等问题。利用信息技…...

编程日记 2025/7/9 13:32:53

GA-Kmeans-Transformer-GRU时序聚类+状态识别组合模型，创新发文无忧！

GA-Kmeans-Transformer-GRU时序聚类状态识别组合模型，创新发文无忧！ 目录 GA-Kmeans-Transformer-GRU时序聚类状态识别组合模型，创新发文无忧！效果一览基本介绍程序设计参考资料效果一览基本介绍 1.GA-Kmeans-Transformer-GRU时…...

编程日记 2025/6/28 20:22:07

Hadoop单机搭建手册

hadoop搭建安装指导手册，包含hadoop-3.1.1、hive-3.1.0、zookeeper-3.4.6、hbase-2.3.0、spark-3.3.0等组件版本。文档详细21页，附带所有软件包。笔者发现很多人对于如何快速高效的单机搭建不太清楚，所以笔者整理了这个文档，希望可…...

编程日记 2025/7/15 6:03:26

【射频IC进阶实践教程】2.6 LNA版图设计及DRC/LVS验证

射频集成电路的版图设计非常关键，他对寄生参数非常敏感，需要使其最小化。还需要注意相互耦合的方式本次课程主要介绍射频IC的一些相关布局和连线方面的考虑。一、版图设计 1. 版图的元件布局首先打开对应的原理图点击进行版图设计由于已经有做好的…...

编程日记 2025/7/15 1:37:45

mac下载安装jdk

背景长时间不折腾mac全部忘记特此记录安装 1.下载jdk 根据需要下载对应的jdk 我直接下载到/Applicatiions目录 https://www.oracle.com/java/technologies/downloads/#java8-mac 2.解压 cd /Applicatiions tar -zxvf jdk-8u431-macosx-x64.tar.gz 3.配置环境 …...

编程日记 2025/7/10 2:05:48

【uniapp】swiper切换时，v-for重新渲染页面导致文字在视觉上的拉扯问题

问题描述先用v-for渲染了几个列表，但这几个列表是占同一个位置的，只是通过切换swiper来显示哪个列表显示，也就是为了优化页面切换时候，没有根据swiper的current再更新v-for的数据，但现在就有个问题，怎么隐…...

编程日记 2025/7/10 1:16:53

shell自动显示当前git的branch

效果简介： 1. 如果没在git仓库，显示无变化 2. 如果在git仓库，显示当前分支实现方法： 在~/.bashrc 里添加： function git_branch { test -d .git && branch"git branch | grep "^\*" | sed…...

编程日记 2025/7/15 1:25:24

使用 Acme.sh 自动生成和续签免费 SSL 证书（含通配符支持）

Acme.sh 是一个开源的脚本，能够从 ZeroSSL、Let’s Encrypt 等证书颁发机构（CA）获取免费的 HTTPS 证书。该脚本特别简单易用，并且支持多种验证方式。下面将详细介绍使用 Acme.sh 生成、安装和更新证书的各个步骤。 Github地址使用…...

编程日记 2025/7/9 23:22:38

【JAVA】Java高级：Spring框架与Java EE—Web开发基础（Servlet、JSP）

Java作为一种广泛使用的编程语言，提供了强大的Web开发框架和技术，其中Servlet和JSP（JavaServer Pages）是构建动态Web应用的基础。了解这些技术对于任何想要深入Java Web开发的程序员来说都是必不可少的。一、Web开发的重要性动…...

编程日记 2025/7/10 16:34:47

pytorch生成对抗网络

# 生成对抗网络 import os import torch import torchvision import torch.nn as nn from torchvision import transforms from torchvision.utils import save_image # Device configuration device torch.device(cuda if torch.cuda.is_available() else cpu) # 超参数 late…...

编程日记 2025/7/14 10:51:51

flask简易版的后端服务创建接口(python)

1.pip install安装Flask和CORS 2.创建http_server.py文件，内容如下 """ ============================ 简易版的后端服务 ============================ """ from flask import Flask, request, jsonify from flask_cors import CORS app = F…...

编程日记 2025/7/9 4:13:42

gitlab 生成并设置 ssh key

一、介绍 🎯 本文主要介绍 SSH Key 的生成方法，以及如何在GitLab上添加SSH Key。GitLab 使用SSH协议与Git 进行安全通信。当您使用 SSH密钥对 GitLab远程服务器进行身份验证时，您不需要每次都提供您的用户名和密码。SSH使用两个密钥&#x…...

编程日记 2025/7/14 9:09:06

ssh远程升级Ubuntu20.04到Ubuntu 22.04

ssh远程升级Ubuntu20.04到Ubuntu 22.04 陈拓 2024/10/16-2024/10/26 1. 简介本文介绍了如何通过ssh将Ubuntu系统从20.04升级到22.04。在进行系统升级之前，建议备份重要数据，以防升级过程中出现问题。 2. 更新当前系统硬件系统架构当前操作系统版…...

编程日记 2025/7/13 11:07:56

Qt开源控件：图像查看器工具V1.1

一、项目概述本项目是一款基于 Qt 框架开发的图像查看工具，可以显示带坐标轴的图像，并实时获取图像中任意像素点的坐标和颜色信息。工具具有图像缩放、动态坐标轴绘制、鼠标交互等功能，使用起来方便直观。二、功能亮点 1. 图像加载与显…...

编程日记 2025/7/14 1:28:28

【WRF-Urban】SLUCM新增空间分布城市冠层参数及人为热排放AHF代码详解（下）

目录详细解释更改文件内容4 运行模块（run）:README.namelist5 输出模块（share）:share/module_check_a_mundo.Fshare/output_wrf.F参考SLUCM新增空间分布城市冠层参数及人为热排放AHF代码详解的前两部分内容可参见-【WRF-Urban】SLUCM新增空间分布城市冠层参数及人为热排放A…...

编程日记 2025/7/9 22:08:01

【C#】新建窗体文件，Form、UserControl

从用途、功能性和架构方面进行描述。 1. 继承自 Form 的窗体（通常是窗口）： 在 C# 中，Form 是用于创建应用程序的主窗口或对话框窗口的类。当您继承自 Form 时，您创建的是一个完整的窗口，可以显示内容、与…...

编程日记 2025/7/15 8:55:42

优化SEO策略掌握长尾关键词的力量

内容概要在数字营销领域，SEO（搜索引擎优化）是帮助网站获得更多流量的关键。然而，随着在线竞争的加剧，单纯依赖短尾关键词已难以满足用户的搜索需求。这时，长尾关键词的引入便显得尤为重要。长尾关键词通常…...

编程日记 2025/7/14 4:09:39

MySQL分页查询

分页查询： 数据记录条数过多的时候，需要分页来显示。语法： select 查询字段 from 表名 where ....等等前面学过的所有写法 limit offset（开始记录索引,是从0开始的）,size（要取出的条数）&…...

编程日记 2025/7/15 2:48:28

执行“go mod tidy”遇到“misbehavior”错误

执行“go mod tidy”报错下错误，执行“go clean -modcache”和删除“go env GOMODCACHE”指定目录均无效： SECURITY ERROR go.sum database server misbehavior detected!old database:go.sum database tree3397826xyyhzdyAOat5li/EXx/MK1gONQf3LAGqArh…...

编程日记 2025/7/9 7:46:51

【机器学习】——windows下安装anaconda并在vscode上进行配置

一、安装anaconda 1.进入清华的镜像网站，下载自己电脑对应的anaconda版本。网站：https://repo.anaconda.com/archive/ 这里我下载的版本是anaconda3-2024.10-1-Windows-x86-64 2.下载完毕后开始安装anaconda 3.配置anaconda环境变量在设置中找到编…...

编程日记 2025/7/13 6:24:44