当前位置: 首页 > 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 系统展示 系统功能结构图 销售经理系统首页图 客户管理图 车辆销…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...