【算法】——二分查找合集
阿华代码,不是逆风,就是我疯
你们的点赞收藏是我前进最大的动力!!
希望本文内容能够帮助到你!!
目录
零:二分查找工具
1:最基础模版
2:mid落点问题
一:最简单的二分
二:查找元素的位置(可能会有多个)
三:搜索插入位置
四:x的平方根
五:山脉数组的峰顶索引
六:寻找峰值
编辑
解法一
解法二
七:点名
零:二分查找工具
1:最基础模版
mid的写法可以防止溢出

2:mid落点问题

巧妙记忆:循环条件为while(left<right)时,left = mid,想象一下,只剩下两个球,那么我们的mid只能落在右端点,否则left = mid 会造成 left < right 死循环,此时我们确定的是右边的界限
重点:left 和right 根据题目的意思进行设置,然后才是mid的设置根据left和right的设置而设置(这才是这个二分查找的精髓所在)
简单记忆:落在哪个端点确定哪个界限
一:最简单的二分
704. 二分查找 - 力扣(LeetCode)

class Solution {public int search(int[] nums, int target) {//mid=left + (right - left)/3//用left移动思想来确定mid的位置,这种写法可以防溢出int left = 0 , right = nums.length-1 , mid = (left+right)/2;while(left<=right){if(nums[mid] < target){left = mid + 1 ;mid = (left+right)/2;}else if(nums[mid] > target){right = mid - 1;mid = (left+right)/2;}else{return mid;}}return -1;}
}
二:查找元素的位置(可能会有多个)
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)


class Solution {public int[] searchRange(int[] nums, int target) {int[] result = new int[]{-1,-1};if(nums.length == 0 ){return result;}//左端点int left = 0 , right = nums.length-1 ,targetLeft = 0 , targetRight = 0;while(left < right){int mid = left + (right - left )/2;if(nums[mid] < target){left = mid + 1;}else{right = mid;}}targetLeft = left;left = 0 ; right = nums.length-1 ;//右端点while(left < right){int mid = left + (right-left+1)/2;if(nums[mid] > target){right = mid - 1;}else{left = mid;}}targetRight = right;if(nums[targetLeft] != target){return result;}else if(nums[targetLeft] == nums[targetRight]){result[0] = targetLeft;result[1] = targetRight;return result;}else{}return result;}
}
三:搜索插入位置
35. 搜索插入位置 - 力扣(LeetCode)



class Solution {public int searchInsert(int[] nums, int target) {if(nums.length == 0){return 0;}int targetLeft = 0 , n = nums.length;int left = 0 , right = nums.length-1;//这道题只用找一个左界限就够了//左界限left = 0 ; right = n-1;while(left < right){int mid = left + (right - left)/2;//左端点if(nums[mid] >= target){right = mid;}else{left = mid + 1;}} targetLeft = left;int result = 0;if(target > nums[targetLeft]){result = targetLeft + 1;}else{result = targetLeft ;}return result;}
}
四:x的平方根
69. x 的平方根 - 力扣(LeetCode)

class Solution {public int mySqrt(int x) {long left = 0 , right = x ;if(x < 1 ){return 0;}long mid = 0;//mid的平方越界了while(left < right){mid = left + (right - left + 1)/2;if(mid * mid <= x){left = mid;}else{right = mid - 1 ;}}return (int)left;//强转为int类型}
}
五:山脉数组的峰顶索引
852. 山脉数组的峰顶索引 - 力扣(LeetCode)


class Solution {public int peakIndexInMountainArray(int[] arr) {int left = 0 , right = arr.length , n = arr.length;while(left < right){int mid = left + (right - left + 1)/2;if(arr[mid] > arr[mid-1]){left = mid;}else if(arr[mid] < arr[mid-1]){right = mid - 1;}else{}}return left;}
}
六:寻找峰值
162. 寻找峰值 - 力扣(LeetCode)

解法一
class Solution {public int findPeakElement(int[] nums) {int left = 0 , right = nums.length-1;//如果数组中只有一个元素,while循环都进不去,规避了这个问题nbwhile(left < right){int mid = left + (right - left )/2;if(nums[mid+1] > nums[mid]){left = mid + 1;}else if(nums[mid+1] < nums[mid]){right = mid;}else{}}return left;}
}
解法二
class Solution {public int findPeakElement(int[] nums) {//暴力解法int n = nums.length , result = 0;if(n == 1){result = 0;}else if(nums[0] > nums[1]){result = 0;}else if(nums[n-1] > nums[n-2]){result = n-1;}else{int left = 0 , right = nums.length ;while(left < right){int mid = left + (right - left + 1)/2;if(nums[mid] > nums[mid-1]){left = mid;}else if(nums[mid] < nums[mid-1]){right = mid-1;}else{}}result = left;}return result;}
}
七:寻找旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值


class Solution {public int findMin(int[] nums) {int left = 0 , n = nums.length , right = n-1;int tem = nums[n-1];while(left < right){int mid = left + (right - left)/2;if(nums[mid] <= nums[n-1]){right = mid;}else{left = mid + 1;}}return nums[left];}
}
七:点名
LCR 173. 点名 - 力扣(LeetCode)


class Solution {public int takeAttendance(int[] records) {int left = 0 , n = records.length , right = records.length-1;if(records[0] != 0){return 0;}if(records[n-1] == n-1){return n;}while(left < right){int mid = left + (right - left)/2;if(records[mid] - mid <= 0){left = mid + 1;}else{right = mid ;}}return right;}
}
相关文章:
【算法】——二分查找合集
阿华代码,不是逆风,就是我疯 你们的点赞收藏是我前进最大的动力!! 希望本文内容能够帮助到你!! 目录 零:二分查找工具 1:最基础模版 2:mid落点问题 一:最…...
社会工程骗局席卷金融机构
2024 年北美金融机构收到的社交工程诈骗报告数量比一年前增加了 10 倍。数据显示,诈骗现在占所有数字银行欺诈的 23%。 深度伪造和 GenAI 诈骗的危险日益增加 BioCatch 在其 2024 年北美数字银行欺诈趋势报告中公布了这些发现,该报告还详细说明了报告的…...
前缀和算法习题篇(上)
1.一维前缀和 题目描述: 解法一:暴力解法:模拟 时间复杂度是O(n*q),会超时。 解法二:前缀和解法:快速求出数组中某一个连续区间的和 快速是指O(1),前缀和思想可把时间复杂度可降到O(q)。 算法思路: 先预处…...
C#核心(9)静态类和静态构造函数
前言 我们先前已经了解了静态成员的基本构成,也简单了解了一下静态变量,现在我们就要来看一下静态类和静态构造函数了,这些其实在上一节我已经在例子里有提到过,相信聪明的你甚至已经发现了一些规律。 GPT对c#中静态类和静态构造…...
B2002 Hello,World! C++实现
Hello,World! 题目描述 编写一个能够输出 Hello,World! 的程序。 提示: 使用英文标点符号;Hello,World! 逗号后面没有空格。H 和 W 为大写字母。 输入格式 输出格式 样例 #1 样例输入 #1 无样例输出 #1 Hello,World!#include <bits/stdc.h&…...
前端-同源与跨域
一、同源策略 两个网站协议名、域名、端口号有一个不同就是非同源,就是跨域。跨域问题就是浏览器的同源策略造成的。 同源是指协议名、域名、端口号 必须完全一致! http 默认端口号是80,https 默认端口号是443 同源策略的限制 一般来说&…...
MySQL远程连接错误解决:Host is not allowed to connect to this MySQL server
1. 异常错误 通过远程客户端访问MySQL服务器时会遇到“Host is not allowed to connect to this MySQL server”的错误提示。 2. 原因 MySQL服务器当前配置不允许来自特定主机的连接尝试。 3. 解决方法 允许远程主机访问MySQL服务器,按照以下步骤操作ÿ…...
详解C语言字符和字符串的输入与输出
字符和字符串的输入与输出 一、字符的输入与输出1.1 字符的输入使用 getchar()使用 scanf() 1.2 字符的输出使用 putchar()使用 printf() 二、字符串的输入与输出2.1 字符串的输入使用 scanf() 输入字符串使用 fgets() 输入字符串 2.2 字符串的输出使用 printf() 输出字符串使用…...
adworld - stack2
adworld - stack2 题目概述:给一个数组(自己控制数组大小和填入的数据),并进行(展示, 增加, 修改值, 求平均值, 退出)菜单选项 存在后门函数(system(“/bin/bash”)),但是没找到栈溢出的点 没判断数组的边界造成任意地址修改 但是如何准确…...
Python学习从0到1 day28 Python 高阶技巧 ⑤ 多线程
若事与愿违,请相信,上天自有安排,允许一切如其所是 —— 24.11.12 一、进程、线程 现代操作系统比如Mac OS X,UNIX,Linux,Windows等,都是支持“多任务”的操作系统。 进程 进程:就…...
nuget 管理全局包、缓存和临时文件夹
查看文件夹位置 dotnet nuget locals all --list清空数据 # Clear the 3.x cache (use either command) dotnet nuget locals http-cache --clear nuget locals http-cache -clear# Clear the 2.x cache (NuGet CLI 3.5 and earlier only) nuget locals packages-cache -clea…...
linux物理内存管理:node,zone,page
一、总览 对于物理内存内存,linux对内存的组织逻辑从上到下依次是:node,zone,page,这些page是根据buddy分配算法组织的,看下面两张图: 上面的概念做下简单的介绍: Node:…...
uniapp 设置安全区域
<!-- 获取安全区域 --> <script setup lang"ts"> import { computed, ref } from vuelet systemType ref(1) // #ifdef APP-PLUS || H5 || APP-PLUS-NVUE systemType.value 1 const { safeAreaInsets } uni.getSystemInfoSync() console.log(safeAre…...
渐进式JavaScript框架Vue 3 入门
目录 前言1. Vue 3 的基础入门1.1 什么是 Vue.js1.2 局部使用 Vue 2. Vue 3 的基本配置2.1 准备 HTML 页面并引入 Vue 模块2.2 创建 Vue 应用实例 3. Vue 的数据绑定与界面渲染3.1 插值表达式 4. 常用指令详解4.1 v-for 指令:列表渲染4.2 v-bind 指令:绑…...
【真题笔记】21年系统架构设计师案例理论点总结
【真题笔记】21年系统架构设计师案例理论点总结 从机器学习定义的灵活性和学习算法的可扩展性,对解释器+管道过滤器+隐式调用进行对比分析!面向对象方法开发软件,建立对象模型+动态模型+功能模型,三者关联关系!数据架构的设计过程包括:数据定义、数据分布、数据管理,三者…...
PostgreSQL的奥秘:深入探究事务与锁的秘密世界
PostgreSQL事务 1. 概述 在数据库系统中,事务(Transaction)是执行数据库操作的最小逻辑单位。它确保了一组操作的完整性和一致性。事务可以通过显式的 BEGIN、COMMIT 和 ROLLBACK 语句块来控制,也可以在自动提交模式(…...
Python进行GRPC和Dubbo协议的高级测试
在微服务架构日益流行的今天,分布式系统的复杂性不断增加。GRPC 和 Dubbo 协议作为当今互联网行业中常见的高性能通信协议,已经成为服务之间交互的核心。然而,随着服务调用层次的不断增加,如何有效地测试这两种协议,确…...
全程云OA系统QCPES.asmx存在SQL注入漏洞
免责声明: 本文旨在提供有关特定漏洞的深入信息,帮助用户充分了解潜在的安全风险。发布此信息的目的在于提升网络安全意识和推动技术进步,未经授权访问系统、网络或应用程序,可能会导致法律责任或严重后果。因此,作者不对读者基于本文内容所采取的任何行为承担责任。读者在…...
从建立TRUST到实现FAIR:可持续海洋经济的数据管理
1. 引言 随着我们对信息管理方式的信任,我们的社会对数字化数据的以来呈指数级增长。为了跟上大数据的需求,通过不断的努力和持续实践,对“good”数据管理方式的共识也在不断发展和演变。 加拿大正在建设国家基础设施和服务以及研究数据管理…...
基于SSM的“汽车销售分析与管理系统”的设计与实现(源码+数据库+文档+PPT)
基于SSM的“汽车销售分析与管理系统”的设计与实现(源码数据库文档PPT) 开发语言:Java 数据库:MySQL 技术:SSM 工具:IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能结构图 销售经理系统首页图 客户管理图 车辆销…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...


