★ 算法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~(∠・ω< )⌒☆ ~ 今天,塞尔达将和大家一起做几道二分查找算法算法题 ~ ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页:椎名澄嵐-CSDN博客 算法专栏:★ 优选算法100天 ★_椎名澄嵐的博客-CSDN博客…...
RTSP RTP RTCP SDP基础知识
理论 流(Streaming ) 是近年在 Internet 上出现的新概念,其定义非常广泛,主要是指通过网络传输多媒体数据的技术总称。 流式传输分为两种 顺序流式传输 (Progressive Streaming) 实时流式传输 (Real time Streaming) …...
静态变量、变量作用域、命名空间
静态变量 静态变量一般位于程序全局data区,只是编程语言根据它所在的scope做语言级别访问限制。 静态变量和全局变量 可以在C语言一个函数中定义static变量,并比较和全局变量的地址差异。 C系语言使用static关键字标示静态变量。 PHP使用大写的STATIC关键…...
Android笔记(二十四)基于Compose组件的MVVM模式和MVI模式的实现
仔细研究了一下MVI(Model-View-Intent)模式,发现它和MVVM模式非常的相识。在采用Android JetPack Compose组件下,MVI模式的实现和MVVM模式的实现非常的类似,都需要借助ViewModel实现业务逻辑和视图数据和状态的传递。在这篇文章中,…...
MySQL 是否支持 XML
MySQL 是否支持 XML:概述与应用 虽然 MySQL 主要以处理关系型数据为主,但它也提供了对 XML 数据的支持。XML(可扩展标记语言)是一种用于数据传输和存储的通用格式。在许多应用场景中,XML 被广泛用于数据交换、配置文件…...
pikachu靶场总结(四)
九、越权漏洞 1.概述 如果使用A用户的权限去操作B用户的数据,A的权限小于B的权限,如果能够成功操作,则称之为越权操作。 越权漏洞形成的原因是后台使用了 不合理的权限校验规则导致的。 一般越权漏洞容易出现在权限页面(需要登…...
24.3 基于文件的服务发现模式
本节重点介绍 : 基于文件的服务发现提供了一种配置静态目标的更通用的方法可以摆脱对特定服务发现源的依赖通常的做法是调用内部CMDB的接口获取target数据,打上标签,生成json文件发给prometheus采集 基于文件的服务发现模式 解决的问题 之前手动配置…...
【Java】面向UDP接口的网络编程
【Java】面向UDP接口的网络编程 一. 基本通信模型二. APIDatagramSocketDatagramPacket 三. 回显服务器/客户端示例服务器客户端总结 一. 基本通信模型 UDP协议是面向数据报的,因此此处要构建数据报(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功能有区别吗
在当今数字时代,管理和备份手机数据变得越来越重要。无论是转移照片、备份短信,还是管理应用程序,一个强大的工具可以大大简化这些操作。iMazing作为一款备受好评的iOS设备管理软件,已经成为许多用户的选择。但是,许多…...
ChatGPT可以分析股票吗?
结合国庆前大A股市的小波牛市以及今天的股市表现,我从多个角度为你提供一些分析和建议: 一、国庆前的小波牛市分析 国庆前,大A股市出现了一波小幅上涨,市场呈现出一些积极的信号: 政策面利好:政府出台了…...
Dockerfile搭建镜像
Dockerfile搭建镜像的优势与区别 引言 在现代软件开发与运维中,容器化技术日益普及,而Docker作为最流行的容器化平台之一,通过Dockerfile提供了一种灵活、自动化的方式来构建Docker镜像。Dockerfile使得镜像的构建过程可重复、可版本化&…...
Kubernetes-Kind篇-01-kind搭建测试集群
1、Kind 介绍 官方文档地址:https://kind.sigs.k8s.io/ github仓库地址:https://github.com/kubernetes-sigs/kind 国内镜像仓库地址:https://gitcode.com/gh_mirrors/ki/kind/overview kind 是一种使用 Docker 容器 nodes 运行本地 Kubern…...
在UniApp中高效处理大量文件请求的策略
在开发跨平台应用时,尤其是在使用UniApp这样的框架时,我们可能会遇到需要同时请求多个文件的情况。然而,不加节制地同时发起大量请求可能会带来严重的性能问题,如界面卡顿、内存溢出、网络带宽饱和等。本文将探讨如何在UniApp中高…...
docker compose入门4—常用命令
在使用 Docker Compose 管理多容器应用时,常见的命令帮助我们高效地管理容器的生命周期、服务、日志等。以下是一些常用的 Docker Compose 命令及其详细讲解: 1. docker-compose up 这个命令用于启动定义在 docker-compose.yml 文件中的服务。 用法&am…...
wps文本框文字居中对齐
直接点对齐里的水平居中,垂直居中是将文本框水平垂直居中,文字不会居中 将文本框里的文字居中: 垂直居中: 水平居中:...
注册信息页面
知识点: !+Enter 直接生成前端基本框架 1.<h1></h1> (2,3,4,5) 表示各级标题 2.<form></form> 表单建立 3.<input type" "></input> 表格(表单嵌套表格) type属…...
详解Java中的BIO、NIO、AIO
1、 详解Java中的BIO、AIO、NIO 1.1、引言 IO流是Java中比较难理解的一个知识点,但是IO流在实际的开发场景中经常会使用到,比如Dubbo底层就是NIO进行通讯。本文将介绍Java发展过程中出现的三种IO:BIO、NIO以及AIO,重点介绍NIO。…...
CAN和CANFD如何转换和通信
随着科技的发展,汽车电子和工业领域中CAN通信需要承载数据量也越来越大,传统CAN通信有了向CANFD通信过渡的倾向。在实现过渡的过程中可能会出现自己设备是CAN通信,客户设备是CANFD通信的情况,或者自己设备是CANFD通信,…...
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…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
云原生周刊:k0s 成为 CNCF 沙箱项目
开源项目推荐 HAMi HAMi(原名 k8s‑vGPU‑scheduler)是一款 CNCF Sandbox 级别的开源 K8s 中间件,通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度,为容器提供统一接口,实现细粒度资源配额…...
