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

★ 算法OJ题 ★ 二分查找算法

Ciallo~(∠・ω< )⌒☆ ~ 今天,塞尔达将和大家一起做几道二分查找算法算法题 ~

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

澄岚主页:椎名澄嵐-CSDN博客

算法专栏:★ 优选算法100天 ★_椎名澄嵐的博客-CSDN博客

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

目录

壹  力扣704 - 二分查找

1.1 题目

1.2 算法解析

1.3 撰写代码

1.4 朴素二分查找模板

贰  力扣34 - 在排序数组中查找元素的第⼀个和最后⼀个位置

2.1 题目

2.2 算法解析

2.3 撰写代码

2.4 二分查找模板

叁  力扣35 - 搜索插入位置

3.1 题目

3.2 算法解析

3.3 撰写代码

肆  力扣69 - x的平方根

4.1 题目

4.2 算法解析

4.3 撰写代码

伍  力扣852 - 山峰数组的峰顶索引

5.1 题目

5.2 算法解析

5.3 撰写代码

陆  力扣162 - 寻找峰值

6.1 题目

6.2 算法解析

6.3 撰写代码

柒  力扣153 - 寻找旋转排序数组中的最小值

7.1 题目

7.2 算法解析

7.3 撰写代码

捌  力扣LCR173 - 点名

8.1 题目

8.2 算法解析

8.3 撰写代码

~ 完 ~


壹  力扣704 - 二分查找

1.1 题目

704. 二分查找 - 力扣(LeetCode)

1.2 算法解析

首先想到的暴力解法就是遍历数组,找到target,时间复杂度为O(N),那么有没有更快速的方法呢~

二分查找算法适用于有二段性的区间,比如一个值的左边比这个值小,右边比此值大,根据数学期望,中间值为最佳~

1.3 撰写代码

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right){// 防止溢出int mid = left + (right - left) / 2;if (nums[mid] > target) right = mid - 1;else if (nums[mid] < target) left = mid + 1;else return mid;}return -1;}
};

1.4 朴素二分查找模板

while(left <= right)
{int mid = left + (right - left) / 2;if (......) right = mid - 1;else if (......) left = mid + 1;else return ......;
}

贰  力扣34 - 在排序数组中查找元素的第⼀个和最后⼀个位置

2.1 题目

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)

2.2 算法解析

2.3 撰写代码

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理数组为空if(nums.size() == 0) return {-1, -1};// 1. 二分左端点int begin = 0;int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}// 判断是否有结果if(nums[left] != target) return {-1, -1};else begin = left; // 记录结果// 2. 二分右端点left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}// 左端点有结果右端点一定有结果return {begin, right};}
};

2.4 二分查找模板

1. 二分左端点模板

while(left < right)
{int mid = left + (right - left) / 2;if(......) left = mid + 1;else right = mid;
}

2. 二分右端点模板

while(left < right)
{int mid = left + (right - left + 1) / 2;if(......) left = mid;else right = mid - 1;
}

叁  力扣35 - 搜索插入位置

3.1 题目

35. 搜索插入位置 - 力扣(LeetCode)

3.2 算法解析

3.3 撰写代码

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] < target) left = mid + 1;else right = mid;}if (nums[left] < target) return left + 1;else return left;}
};

肆  力扣69 - x的平方根

4.1 题目

69. x 的平方根 - 力扣(LeetCode)

4.2 算法解析

此题需要考虑边界情况, <1单独处理~

并且数据过大有溢出风险,要用long long来存~

4.3 撰写代码

class Solution {
public:int mySqrt(int x) {if(x < 1) return 0; // 边界情况~int left = 1, right = x;while(left < right){long long mid = left + (right - left + 1) / 2; // 防溢出if(mid * mid <= x) left = mid;else right = mid - 1;}return left;}
};

伍  力扣852 - 山峰数组的峰顶索引

5.1 题目

852. 山脉数组的峰顶索引 - 力扣(LeetCode)

5.2 算法解析

5.3 撰写代码

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size() - 2;while(left < right){int mid = left + (right - left + 1) / 2;if(arr[mid] > arr[mid - 1]) left = mid;else right = mid - 1;}return left;}
};

陆  力扣162 - 寻找峰值

6.1 题目

162. 寻找峰值 - 力扣(LeetCode)

6.2 算法解析

无序数组有二段性时也可以使用二分查找算法~

6.3 撰写代码

class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > nums[mid + 1]) right = mid;else left = mid + 1;}return left;}
};

柒  力扣153 - 寻找旋转排序数组中的最小值

7.1 题目

153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

7.2 算法解析

7.3 撰写代码

class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;int n = nums[right];while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > n) left = mid + 1;else right = mid;}return nums[left];}
};

捌  力扣LCR173 - 点名

8.1 题目

LCR 173. 点名 - 力扣(LeetCode)

8.2 算法解析

8.3 撰写代码

class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0, right = records.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (records[mid] == mid) left = mid + 1;else right = mid;}if(records[left] == left) return left + 1;else return left;}
};

~ 完 ~

相关文章:

★ 算法OJ题 ★ 二分查找算法

Ciallo&#xff5e;(∠・ω< )⌒☆ ~ 今天&#xff0c;塞尔达将和大家一起做几道二分查找算法算法题 ~ ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页&#xff1a;椎名澄嵐-CSDN博客 算法专栏&#xff1a;★ 优选算法100天 ★_椎名澄嵐的博客-CSDN博客…...

RTSP RTP RTCP SDP基础知识

理论 流&#xff08;Streaming &#xff09; 是近年在 Internet 上出现的新概念&#xff0c;其定义非常广泛&#xff0c;主要是指通过网络传输多媒体数据的技术总称。 流式传输分为两种 顺序流式传输 (Progressive Streaming) 实时流式传输 (Real time Streaming) ​​​​​…...

静态变量、变量作用域、命名空间

静态变量 静态变量一般位于程序全局data区&#xff0c;只是编程语言根据它所在的scope做语言级别访问限制。 静态变量和全局变量 可以在C语言一个函数中定义static变量&#xff0c;并比较和全局变量的地址差异。 C系语言使用static关键字标示静态变量。 PHP使用大写的STATIC关键…...

Android笔记(二十四)基于Compose组件的MVVM模式和MVI模式的实现

仔细研究了一下MVI(Model-View-Intent)模式&#xff0c;发现它和MVVM模式非常的相识。在采用Android JetPack Compose组件下&#xff0c;MVI模式的实现和MVVM模式的实现非常的类似&#xff0c;都需要借助ViewModel实现业务逻辑和视图数据和状态的传递。在这篇文章中&#xff0c…...

MySQL 是否支持 XML

MySQL 是否支持 XML&#xff1a;概述与应用 虽然 MySQL 主要以处理关系型数据为主&#xff0c;但它也提供了对 XML 数据的支持。XML&#xff08;可扩展标记语言&#xff09;是一种用于数据传输和存储的通用格式。在许多应用场景中&#xff0c;XML 被广泛用于数据交换、配置文件…...

pikachu靶场总结(四)

九、越权漏洞 1.概述 如果使用A用户的权限去操作B用户的数据&#xff0c;A的权限小于B的权限&#xff0c;如果能够成功操作&#xff0c;则称之为越权操作。 越权漏洞形成的原因是后台使用了 不合理的权限校验规则导致的。 一般越权漏洞容易出现在权限页面&#xff08;需要登…...

24.3 基于文件的服务发现模式

本节重点介绍 : 基于文件的服务发现提供了一种配置静态目标的更通用的方法可以摆脱对特定服务发现源的依赖通常的做法是调用内部CMDB的接口获取target数据&#xff0c;打上标签&#xff0c;生成json文件发给prometheus采集 基于文件的服务发现模式 解决的问题 之前手动配置…...

【Java】面向UDP接口的网络编程

【Java】面向UDP接口的网络编程 一. 基本通信模型二. APIDatagramSocketDatagramPacket 三. 回显服务器/客户端示例服务器客户端总结 一. 基本通信模型 UDP协议是面向数据报的&#xff0c;因此此处要构建数据报(Datagram)在进行发送。 二. API DatagramSocket DatagramSocke…...

SRS服务器搭建

1、配置 listen 1935; max_connections 1000; #srs_log_tank file; #srs_log_file ./objs/srs.log; daemon on; http_api { enabled on; listen 1985; } http_server { enabled on; listen 808…...

iMazing只能苹果电脑吗 Win和Mac上的iMazing功能有区别吗

在当今数字时代&#xff0c;管理和备份手机数据变得越来越重要。无论是转移照片、备份短信&#xff0c;还是管理应用程序&#xff0c;一个强大的工具可以大大简化这些操作。iMazing作为一款备受好评的iOS设备管理软件&#xff0c;已经成为许多用户的选择。但是&#xff0c;许多…...

ChatGPT可以分析股票吗?

结合国庆前大A股市的小波牛市以及今天的股市表现&#xff0c;我从多个角度为你提供一些分析和建议&#xff1a; 一、国庆前的小波牛市分析 国庆前&#xff0c;大A股市出现了一波小幅上涨&#xff0c;市场呈现出一些积极的信号&#xff1a; 政策面利好&#xff1a;政府出台了…...

Dockerfile搭建镜像

Dockerfile搭建镜像的优势与区别 引言 在现代软件开发与运维中&#xff0c;容器化技术日益普及&#xff0c;而Docker作为最流行的容器化平台之一&#xff0c;通过Dockerfile提供了一种灵活、自动化的方式来构建Docker镜像。Dockerfile使得镜像的构建过程可重复、可版本化&…...

Kubernetes-Kind篇-01-kind搭建测试集群

1、Kind 介绍 官方文档地址&#xff1a;https://kind.sigs.k8s.io/ github仓库地址&#xff1a;https://github.com/kubernetes-sigs/kind 国内镜像仓库地址&#xff1a;https://gitcode.com/gh_mirrors/ki/kind/overview kind 是一种使用 Docker 容器 nodes 运行本地 Kubern…...

在UniApp中高效处理大量文件请求的策略

在开发跨平台应用时&#xff0c;尤其是在使用UniApp这样的框架时&#xff0c;我们可能会遇到需要同时请求多个文件的情况。然而&#xff0c;不加节制地同时发起大量请求可能会带来严重的性能问题&#xff0c;如界面卡顿、内存溢出、网络带宽饱和等。本文将探讨如何在UniApp中高…...

docker compose入门4—常用命令

在使用 Docker Compose 管理多容器应用时&#xff0c;常见的命令帮助我们高效地管理容器的生命周期、服务、日志等。以下是一些常用的 Docker Compose 命令及其详细讲解&#xff1a; 1. docker-compose up 这个命令用于启动定义在 docker-compose.yml 文件中的服务。 用法&am…...

wps文本框文字居中对齐

直接点对齐里的水平居中&#xff0c;垂直居中是将文本框水平垂直居中&#xff0c;文字不会居中 将文本框里的文字居中&#xff1a; 垂直居中&#xff1a; 水平居中&#xff1a;...

注册信息页面

知识点&#xff1a; &#xff01;&#xff0b;Enter 直接生成前端基本框架 1.<h1></h1> (2,3,4,5) 表示各级标题 2.<form></form> 表单建立 3.<input type" "></input> 表格&#xff08;表单嵌套表格&#xff09; type属…...

详解Java中的BIO、NIO、AIO

1、 详解Java中的BIO、AIO、NIO 1.1、引言 IO流是Java中比较难理解的一个知识点&#xff0c;但是IO流在实际的开发场景中经常会使用到&#xff0c;比如Dubbo底层就是NIO进行通讯。本文将介绍Java发展过程中出现的三种IO&#xff1a;BIO、NIO以及AIO&#xff0c;重点介绍NIO。…...

CAN和CANFD如何转换和通信

随着科技的发展&#xff0c;汽车电子和工业领域中CAN通信需要承载数据量也越来越大&#xff0c;传统CAN通信有了向CANFD通信过渡的倾向。在实现过渡的过程中可能会出现自己设备是CAN通信&#xff0c;客户设备是CANFD通信的情况&#xff0c;或者自己设备是CANFD通信&#xff0c;…...

QDateTimeEdit Class

Header:#include qmake:QT += widgets Inherits:QAbstractSpinBox Inherited By:QDateEdit and QTimeEdit Public Types enum Section {NoSection, AmPmSection, MSecSection, SecondSection, MinuteSection, …, YearSection } flags SectionsProperties calendarPopu…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...