【算法】——二分查找合集
阿华代码,不是逆风,就是我疯
你们的点赞收藏是我前进最大的动力!!
希望本文内容能够帮助到你!!
目录
零:二分查找工具
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 系统展示 系统功能结构图 销售经理系统首页图 客户管理图 车辆销…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案
一、延迟敏感行业面临的DDoS攻击新挑战 2025年,金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征: AI驱动的自适应攻击:攻击流量模拟真实用户行为,差异率低至0.5%,传统规则引…...


