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

【算法】——二分查找合集

8e19eee2be5648b78d93fbff2488137b.png

阿华代码,不是逆风,就是我疯

你们的点赞收藏是我前进最大的动力!!

希望本文内容能够帮助到你!!

目录

零:二分查找工具

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;}
}

相关文章:

【算法】——二分查找合集

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 零&#xff1a;二分查找工具 1&#xff1a;最基础模版 2&#xff1a;mid落点问题 一&#xff1a;最…...

社会工程骗局席卷金融机构

2024 年北美金融机构收到的社交工程诈骗报告数量比一年前增加了 10 倍。数据显示&#xff0c;诈骗现在占所有数字银行欺诈的 23%。 深度伪造和 GenAI 诈骗的危险日益增加 BioCatch 在其 2024 年北美数字银行欺诈趋势报告中公布了这些发现&#xff0c;该报告还详细说明了报告的…...

前缀和算法习题篇(上)

1.一维前缀和 题目描述&#xff1a; 解法一&#xff1a;暴力解法&#xff1a;模拟 时间复杂度是O(n*q),会超时。 解法二&#xff1a;前缀和解法&#xff1a;快速求出数组中某一个连续区间的和 快速是指O(1),前缀和思想可把时间复杂度可降到O(q)。 算法思路&#xff1a; 先预处…...

C#核心(9)静态类和静态构造函数

前言 我们先前已经了解了静态成员的基本构成&#xff0c;也简单了解了一下静态变量&#xff0c;现在我们就要来看一下静态类和静态构造函数了&#xff0c;这些其实在上一节我已经在例子里有提到过&#xff0c;相信聪明的你甚至已经发现了一些规律。 GPT对c#中静态类和静态构造…...

B2002 Hello,World! C++实现

Hello,World! 题目描述 编写一个能够输出 Hello,World! 的程序。 提示&#xff1a; 使用英文标点符号&#xff1b;Hello,World! 逗号后面没有空格。H 和 W 为大写字母。 输入格式 输出格式 样例 #1 样例输入 #1 无样例输出 #1 Hello,World!#include <bits/stdc.h&…...

前端-同源与跨域

一、同源策略 两个网站协议名、域名、端口号有一个不同就是非同源&#xff0c;就是跨域。跨域问题就是浏览器的同源策略造成的。 同源是指协议名、域名、端口号 必须完全一致&#xff01; http 默认端口号是80&#xff0c;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服务器&#xff0c;按照以下步骤操作&#xff…...

详解C语言字符和字符串的输入与输出

字符和字符串的输入与输出 一、字符的输入与输出1.1 字符的输入使用 getchar()使用 scanf() 1.2 字符的输出使用 putchar()使用 printf() 二、字符串的输入与输出2.1 字符串的输入使用 scanf() 输入字符串使用 fgets() 输入字符串 2.2 字符串的输出使用 printf() 输出字符串使用…...

adworld - stack2

adworld - stack2 题目概述&#xff1a;给一个数组(自己控制数组大小和填入的数据)&#xff0c;并进行(展示, 增加, 修改值, 求平均值, 退出)菜单选项 存在后门函数(system(“/bin/bash”))&#xff0c;但是没找到栈溢出的点 没判断数组的边界造成任意地址修改 但是如何准确…...

Python学习从0到1 day28 Python 高阶技巧 ⑤ 多线程

若事与愿违&#xff0c;请相信&#xff0c;上天自有安排&#xff0c;允许一切如其所是 —— 24.11.12 一、进程、线程 现代操作系统比如Mac OS X&#xff0c;UNIX&#xff0c;Linux&#xff0c;Windows等&#xff0c;都是支持“多任务”的操作系统。 进程 进程&#xff1a;就…...

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

一、总览 对于物理内存内存&#xff0c;linux对内存的组织逻辑从上到下依次是&#xff1a;node&#xff0c;zone&#xff0c;page&#xff0c;这些page是根据buddy分配算法组织的&#xff0c;看下面两张图&#xff1a; 上面的概念做下简单的介绍&#xff1a; Node&#xff1a…...

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 指令&#xff1a;列表渲染4.2 v-bind 指令&#xff1a;绑…...

【真题笔记】21年系统架构设计师案例理论点总结

【真题笔记】21年系统架构设计师案例理论点总结 从机器学习定义的灵活性和学习算法的可扩展性,对解释器+管道过滤器+隐式调用进行对比分析!面向对象方法开发软件,建立对象模型+动态模型+功能模型,三者关联关系!数据架构的设计过程包括:数据定义、数据分布、数据管理,三者…...

PostgreSQL的奥秘:深入探究事务与锁的秘密世界

PostgreSQL事务 1. 概述 在数据库系统中&#xff0c;事务&#xff08;Transaction&#xff09;是执行数据库操作的最小逻辑单位。它确保了一组操作的完整性和一致性。事务可以通过显式的 BEGIN、COMMIT 和 ROLLBACK 语句块来控制&#xff0c;也可以在自动提交模式&#xff08…...

Python进行GRPC和Dubbo协议的高级测试

在微服务架构日益流行的今天&#xff0c;分布式系统的复杂性不断增加。GRPC 和 Dubbo 协议作为当今互联网行业中常见的高性能通信协议&#xff0c;已经成为服务之间交互的核心。然而&#xff0c;随着服务调用层次的不断增加&#xff0c;如何有效地测试这两种协议&#xff0c;确…...

全程云OA系统QCPES.asmx存在SQL注入漏洞

免责声明: 本文旨在提供有关特定漏洞的深入信息,帮助用户充分了解潜在的安全风险。发布此信息的目的在于提升网络安全意识和推动技术进步,未经授权访问系统、网络或应用程序,可能会导致法律责任或严重后果。因此,作者不对读者基于本文内容所采取的任何行为承担责任。读者在…...

从建立TRUST到实现FAIR:可持续海洋经济的数据管理

1. 引言 随着我们对信息管理方式的信任&#xff0c;我们的社会对数字化数据的以来呈指数级增长。为了跟上大数据的需求&#xff0c;通过不断的努力和持续实践&#xff0c;对“good”数据管理方式的共识也在不断发展和演变。 加拿大正在建设国家基础设施和服务以及研究数据管理…...

基于SSM的“汽车销售分析与管理系统”的设计与实现(源码+数据库+文档+PPT)

基于SSM的“汽车销售分析与管理系统”的设计与实现&#xff08;源码数据库文档PPT) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SSM 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能结构图 销售经理系统首页图 客户管理图 车辆销…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...