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

【数据结构与算法】LeetCode:二分查找

文章目录

  • 二分查找
    • 二分查找
    • 搜索插入位置 (Hot 100)
    • x 的平方根
    • 搜索二维矩阵(Hot 100)
    • 在排序数组中查找元素的第一个和最后一个位置 (Hot 100)
    • 搜索旋转排序数组 (Hot 100)
    • 寻找旋转排序数组中的最小值 (Hot 100)

二分查找

二分查找

二分查找

class Solution{
public:int search(vector<int>& nums, int target){// 设定左闭右闭的区间int left = 0;  int right = nums.size() - 1;while (left <= right){  // 闭区间查找,left == right依然有效,所以用<=int middle = left + (right-left) / 2; // 中值索引if (nums[middle] > target){   right = middle-1;   // target在左边,更新右上限}else if (nums[middle] < target){left = middle + 1;  // target在右边,更新左上限}else{return middle;    // 找到target,返回下标}}return -1;}};

搜索插入位置 (Hot 100)

搜索插入位置

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int n = nums.size();int left = 0, right = n - 1, ans = n;while(left <= right){ int mid = ((right - left) >> 1) + left;if(nums[mid] > target){  right = mid - 1;}else if (nums[mid] < target){left = mid + 1;}else{return mid;}}// left此时 > right// left指向的是第一个大于target的元素的索引return left;}
};

x 的平方根

x 的平方根

class Solution {
public:int mySqrt(int x) {int l = 0, r = x;while (l <= r) {int mid = l + (r - l) / 2;if ((long long) mid * mid < x) { l = mid + 1;} else if ((long long) mid * mid > x) {r = mid - 1;}else{return mid;}}// l此时 > r,向下取整return r;}
};

搜索二维矩阵(Hot 100)

搜索二维矩阵

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int left = 0, right = m * n - 1;while(left <= right){int mid = (right - left >> 2) + left;int x = matrix[mid / n][mid % n];if(x < target){left = mid + 1;}  else if(x > target){right = mid - 1;} else{return true;}}return false;}
};

在排序数组中查找元素的第一个和最后一个位置 (Hot 100)

在排序数组中查找元素的第一个和最后一个位置

#include <vector>
using namespace std;class Solution {
public:int binarySearch(vector<int>& nums, int target) {// 二分查找变形int left = 0, right = nums.size() - 1, ans = -1;while (left <= right) {int mid = left + ((right - left) >> 1);if (nums[mid] == target) {ans = mid;right = mid - 1; // 找到目标值时,继续在左半部分查找} else if (nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return ans;}vector<int> searchRange(vector<int>& nums, int target) {// 调用binarySearch函数,查找目标值的第一个位置int first_pos = binarySearch(nums, target);if (first_pos == -1) return vector<int>{-1, -1};// 查找目标值的最后一个位置int last_pos = first_pos;while (last_pos < nums.size() && nums[last_pos] == target) last_pos++;last_pos--;return vector<int>{first_pos, last_pos};}
};

搜索旋转排序数组 (Hot 100)

搜索旋转排序数组

//定理一:只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。
//定理二:判断顺序区间还是乱序区间,只需要对比 left 和 right 是否是顺序对即可,left <= right,顺序区间,否则乱序区间。
//定理三:每次二分都会至少存在一个顺序区间。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) return mid;if (nums[left] <= nums[mid]) {  // left 到 mid 是顺序区间(target >= nums[left] && target < nums[mid]) ? right = mid - 1 : left = mid + 1;// 如果target在顺序区间,修改区间右边界; 如果不在,修改搜索左边界}else {  // mid 到 right 是顺序区间(target > nums[mid] && target <= nums[right]) ? left = mid + 1 : right = mid - 1;// 如果target在顺序区间,修改区间左边界; 如果不在,修改搜索右边界}}return -1;}
};

寻找旋转排序数组中的最小值 (Hot 100)

寻找旋转排序数组中的最小值

class Solution {  
public:  int findMin(vector<int>& nums) {  int low = 0;  int high = nums.size() - 1;  while (low < high) {  int pivot = low + (high - low) / 2;  // 如果pivot位置的值小于high位置的值,说明最小值在pivot和low之间(包括pivot)  if (nums[pivot] <= nums[high])  high = pivot;   // 否则,最小值在pivot和high之间(不包括pivot)  else  low = pivot + 1;  // (nums[pivot] > nums[high])}  // 当low和high相等时,说明已经找到了最小值,返回该值  return nums[high];  }  
};

if (nums[pivot] < nums[high])
在这里插入图片描述

else:

相关文章:

【数据结构与算法】LeetCode:二分查找

文章目录 二分查找二分查找搜索插入位置 &#xff08;Hot 100&#xff09;x 的平方根搜索二维矩阵&#xff08;Hot 100&#xff09;在排序数组中查找元素的第一个和最后一个位置 &#xff08;Hot 100&#xff09;搜索旋转排序数组 &#xff08;Hot 100&#xff09;寻找旋转排序…...

专题·大模型安全 | 生成式人工智能的内容安全风险与应对策略

正如一枚硬币的两面&#xff0c;生成式人工智能大模型&#xff08;以下简称“生成式大模型”&#xff09;在助力内容生成的同时也潜藏风险&#xff0c;成为虚假信息传播、数据隐私泄露等问题的温床&#xff0c;加剧了认知域风险。与传统人工智能&#xff08;AI&#xff09;相比…...

CORS跨域+Nginx配置、Apache配置

CORS&#xff08;Cross-Origin Resource Sharing&#xff0c;跨源资源共享&#xff09;是一种机制&#xff0c;它使用额外的HTTP头部来告诉浏览器允许一个网页运行的脚本从不同于它自身来源的服务器上请求资源&#xff08;例如字体、JavaScript、CSS等&#xff09;。这是一种安…...

文件查找和打包压缩【1.7】

文件查找和打包压缩【1.7】 八、文件查找和打包压缩8.1 文件查找8.1.1 locate8.1.2 findfind8.1.2.1 指定搜索目录层级8.1.2.2 先处理文件再处理目录8.1.2.3 根据文件名和inode查找8.1.2.4 根据属主属组查找8.1.2.5 根据文件类型查找8.1.2.6 空文件或目录8.1.2.7 组合条件8.1.2…...

速盾:cdn一般多长时间清理下缓存?

CDN&#xff08;Content Delivery Network&#xff09;是一种网络加速技术&#xff0c;通过将网站的静态资源&#xff08;如图片、视频、CSS、JavaScript等&#xff09;分布到全球各地的服务器节点上&#xff0c;从而提高用户访问这些资源的速度和体验。CDN还具备缓存功能&…...

react hooks--useRef

基本用法 在类组件中获取一个dom元素实例&#xff0c;可以通过React.CreateRef或者回调函数的方式去获取。语法&#xff1a;const refContainer useRef(initialValue);使用场景&#xff1a;在 React 中进行 DOM 操作时&#xff0c;用来获取 DOM作用&#xff1a;返回一个带有 …...

GPT对话知识库——将寄存器中的一位数据读到变量中需要什么步骤?C语言中掩码的作用。

目录 1&#xff0c;问&#xff1a; 1&#xff0c;答&#xff1a; 1. 确定目标寄存器地址 2. 定位目标位 位操作的基本步骤&#xff1a; 3. 示例代码 示例步骤&#xff1a; 4. 详细解释步骤 5. 举例 6. 常见用法 总结 注&#xff1a; C语言中掩码的作用&#xff1a…...

【计算机网络】运输层协议解析

前言 运输层直接为应用进程间的逻辑通信提供服务。运输层向高层用户屏蔽了下面网络核心细节&#xff08;如网络拓扑、路由选择协议等&#xff09;它使应用进程看见的就好像是在两个运输层实体之间有一条端到端的逻辑通信信道。 UDP与TCP对比 UDP&#xff1a; 无连接 支持一对…...

Redis存储原理

前言 我们从redis服务谈起&#xff0c;redis是单reactor&#xff0c;命令在redis-server线程处理。还有若干读写IO线程负责IO操作&#xff08;redis6.0之后&#xff0c;Redis之pipeline与事务&#xff09;。此外还有一个内存池线程负责内存管理、一个后台文件线程负责大文件的关…...

PHP、Java等其他语言转Go时选择GoFly快速快速开发框架指南

概要 经过一年多的发展GoFly快速开发框架已被一千多家科技企业或开发者用于项目开发&#xff0c;它的简单易学得到其他语言转Go首选框架。且企业版的发展为GoFly社区提供资金&#xff0c;这使得GoFly快速框架得到良好的发展&#xff0c;GoFly技术团队加大投入反哺科技企业和开…...

【MySQL】获取最近7天和最近14天的订单数量,使用MySQL详细写出,使用不同的方法

1. 获取最近7天和最近14天的订单数量&#xff0c;使用MySQL详细写出&#xff0c;使用不同的方法 要获取最近7天和最近14天的订单数量&#xff0c;我们可以使用不同的方法来优化查询性能。以下是两种方法&#xff1a; 1.1 方法一&#xff1a;使用日期计算 SELECTSUM(CASE WHE…...

WebView2新增、修改、删除、禁用右键菜单相关操作。

参考链接&#xff1a;WebView2操作右键菜单...

使用vue创建项目

一、安装环境 二、创建vue框架&#xff08;创建文件夹&#xff0c;摁shift鼠标右键 打开&#xff09; 1、项目配置 2、新增目录 三、路径别名配置 输入/ ,VSCode会联想出src下的所有子目录和文件&#xff0c;统一文件路径访问时不容易出错 四、ElementPlus配置 1、组件分为…...

Apache CVE-2021-41773 漏洞攻略

漏洞简介 该漏洞是由于Apache HTTP Server 2.4.49版本存在⽬录穿越漏洞,在路径穿越⽬录 <Directory/>Require all granted</Directory>允许被访问的的情况下&#xff08;默认开启&#xff09;&#xff0c;攻击者可利⽤该路径穿越漏洞读取到Web⽬录之外的其他⽂件在…...

【redis-02】深入理解redis中RBD和AOF的持久化

redis系列整体栏目 内容链接地址【一】redis基本数据类型和使用场景https://zhenghuisheng.blog.csdn.net/article/details/142406325【二】redis的持久化机制和原理https://zhenghuisheng.blog.csdn.net/article/details/142441756 如需转载&#xff0c;请输入&#xff1a;htt…...

亚马逊IP关联揭秘:发生ip关联如何处理

在亚马逊这一全球领先的电商平台上&#xff0c;IP关联是一个不可忽视的问题&#xff0c;尤其是对于多账号运营的卖家而言。本文将深入解析亚马逊IP关联的含义、影响以及应对策略&#xff0c;帮助卖家更好地理解和应对这一问题。 什么是亚马逊IP关联&#xff1f; 亚马逊IP关联…...

jQuery Mobile 弹窗

jQuery Mobile 弹窗 引言 在移动设备上,弹窗是一种常见的用户界面元素,用于显示信息、获取用户输入或提供特定功能。jQuery Mobile 是一个流行的移动框架,它提供了丰富的组件来帮助开发者创建响应式的移动界面。本文将重点介绍如何在 jQuery Mobile 中使用弹窗(Popup)组…...

【macOS】【zsh报错】zsh: command not found: python

【macOS】【zsh Error】zsh: command not found: python 本地已经安装了Python&#xff0c;且能在Pycharm中编译Python程序并运行。 但是&#xff0c;在macOS终端&#xff0c;运行Python&#xff0c;报错。 首先要确认你在macOS系统下&#xff0c;是否安装了Python。 如果安…...

NoSql数据库Redis知识点

数据库的分类 关系型数据库 &#xff0c;是建立在关系模型基础上的数据库&#xff0c;其借助于集合代数等数学概念和方法来处理数据库 中的数据主流的 MySQL 、 Oracle 、 MS SQL Server 和 DB2 都属于这类传统数据库。 NoSQL 数据库 &#xff0c;全称为 Not Only SQL &a…...

Redis 使用指南

Redis 使用指南 概述 Redis 是一个开源的、基于内存的数据结构存储系统&#xff0c;可以用作数据库、缓存和消息中间件。它支持多种类型的数据结构&#xff0c;如字符串&#xff08;strings&#xff09;、哈希&#xff08;hashes&#xff09;、列表&#xff08;lists&#xf…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...