当前位置: 首页 > 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…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...

shell脚本质数判断

shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数&#xff09;shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数&#xff09; 思路&#xff1a; 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...

ffmpeg(三):处理原始数据命令

FFmpeg 可以直接处理原始音频和视频数据&#xff08;Raw PCM、YUV 等&#xff09;&#xff0c;常见场景包括&#xff1a; 将原始 YUV 图像编码为 H.264 视频将 PCM 音频编码为 AAC 或 MP3对原始音视频数据进行封装&#xff08;如封装为 MP4、TS&#xff09; 处理原始 YUV 视频…...