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

【算法——二分查找】

理论基础:

程序员面试经典题,二分搜索一个区间,区间查找 (LeetCode 34)_哔哩哔哩_bilibili

手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode:704. 二分查找_哔哩哔哩_bilibili

这个是红蓝法,很牛:二分查找为什么总是写错?_哔哩哔哩_bilibili

在二分查找中,计算中间位置使用mid = left + (right - left) / 2而不是mid = (left + right) / 2主要是为了避免整数溢出的问题。

此类型题目多样总结:

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

因为二分无法查到起止位置;所以用两次二分,一次左边界,一次右边界;

会不会漏查问题:比如left左边会不会还有target

#include<iostream>
using namespace std;
#include<vector>
int main()
{vector<int>nums = { 2,2 };int target = 3;int l = -1, r = nums.size();while (l + 1 != r)    //找第一个target{int m = l + (r - l) / 2;if (nums[m] < target) l = m;else r = m;}if (r >= nums.size() || nums[r] != target) return -1;cout << "l:" << l << "  r:" << r << endl;      //r就是第一个targetl = -1; r = nums.size();while (l + 1 != r)  //找最后一个target{int m = l + (r - l) / 2;if (nums[m] <= target) l = m;else r = m;}cout << "l:" << l << "  r:" << r << endl;      //l就是最后一个targetreturn 0;
}

35. 搜索插入位置

#include<iostream>
using namespace std;
#include<vector>
int main()
{vector<int>nums = { 1,3,5,6 };int l = -1, r = nums.size();int target = 7;while (l + 1 != r){int m = l + (r - l) / 2;if (nums[m] >= target) r = m;   //核心else l = m;}cout << r;return 0;
}

69. x 的平方根 

相关文章:

【算法——二分查找】

理论基础&#xff1a; 程序员面试经典题&#xff0c;二分搜索一个区间&#xff0c;区间查找 (LeetCode 34)_哔哩哔哩_bilibili 手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode&#xff1a;704. 二分查找_哔哩哔哩_bilibili 这个是红蓝法&#xff0c;很牛…...

Cisco Packet Tracer的安装加汉化

这个工具学计算机网络的同学会用到 1.下载安装 网盘链接&#xff1a;https://pan.baidu.com/s/1CmnxAD9MkCtE7pc8Tjw0IA 提取码&#xff1a;frkb 点击第一个进行安装&#xff0c;按步骤来即可。 2.汉化 &#xff08;1&#xff09;复制chinese.ptl文件 &#xff08;2&…...

MMain函数定义为WinMain函数看port1632.h和pwin32.h文件

编译win2k3的源代码的时候有时候看到MMain函数 ..//public/sdk/inc/port1632.h #if defined(WIN16) /* ---------------- Maps to windows 3.0 and 3.1 16-bit APIs ----------------*/ #include "ptypes16.h" #include "pwin16.h" #include "plan16.…...

单词搜索问题(涉及递归等)

目录 一题目&#xff1a; 二思路解释&#xff1a; 三解答代码&#xff1a; 一题目&#xff1a; newcode题目链接&#xff1a; 单词搜索_牛客题霸_牛客网 二思路解释&#xff1a; 思路&#xff1a;个人理解是找到word中的第一个元素&#xff0c;然后去递归的上下左右查找&am…...

Redis的一些通用指令

首先我们需要先连接客户端服务器&#xff0c;此时我们需要通过redis-cli和redis服务器进行交互&#xff0c;输入ping来确保通路的流畅 &#xff08;一&#xff09;get和set redis中最核心的两个命令就是get和set&#xff0c;get就是根据key来取出对应value&#xff0c;set就是把…...

C++中vector类的使用

目录 1.vector类常用接口说明 1.1默认成员函数 1.1.1构造函数(constructor) 1.1.2 赋值运算符重载(operator()) 2. vector对象的访问及遍历操作(Iterators and Element access) 3.vector类对象的容量操作(Capacity) 4. vector类对象的修改及相关操作(Modifiers and Stri…...

cmaklist流程控制——调试及发布

cmaklist流程控制 目前只会配置-编译调试-打包发布&#xff0c;并且不会workflow控制 后续学习配置-编译调试-测试-打包发布&#xff0c;workflow控制&#xff0c;理解整个流程&#xff0c;目前对流程控制理解也不够。 1.CMake Presets 先于Cmakelist文件&#xff0c;指导项…...

制作一个能对话能跳舞的otto机器人

OTTO机器人是一个开源外壳&#xff0c;硬件和软件的桌面机器人项目&#xff0c;非常适合新手研究和拓展。记住&#xff0c;他是一个能移动有表情能声音的机器人。 b站有很多演示和组装的视频&#xff0c;我就不多说了&#xff0c;照着做就好&#xff0c;因为硬件我也是刚入门&…...

git配置SSH

1 打开cmd窗口 2 在窗口中输入如下命令&#xff1a; 配置用户名&#xff1a; git config --global user.name “gyk” 配置邮箱&#xff1a; git config --global user.email “247929163qq.com” 继续在Git命令窗口中输入如下命令&#xff0c;即可生成SSH公钥和私钥 ss…...

mozilla/pdf.js view.html加载指定页码

mozilla/pdf.js view.html加载指定页码 在Mozilla’s PDF.js中&#xff0c;如果你想要在viewer.html加载时直接跳转到指定的页码&#xff0c;你可以通过修改URL来实现。 PDF.js使用查询参数来处理URL&#xff0c;其中page参数用于指定页码。你可以通过修改URL的查询字符串来设…...

Qt之QFuture理解

结构 #mermaid-svg-J9J683RG8QjtEqoM {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-J9J683RG8QjtEqoM .error-icon{fill:#552222;}#mermaid-svg-J9J683RG8QjtEqoM .error-text{fill:#552222;stroke:#552222;}#merm…...

求二叉树的高度(递归和非递归)

假设二叉树采用二叉链表存储结构&#xff0c;设计一个算法求二叉树的高度。 递归&#xff1a; int getTreeHight(BiTree T){if(TNULL){return 0;}else {int lh getTreeHight(T->lchild);int rh getTreeHight(T->rchild);return (lh>rh?lh:rh)1;}}时间复杂度O(n)&a…...

Java查找算法——(四)分块查找(完整详解,附有代码+案例)

文章目录 分块查找1.1普通分块查找 分块查找 1.1普通分块查找 分块原则&#xff1a; 块内无序&#xff0c;块间有序:前一块中的最大数据&#xff0c;小于后一块中所有的数据&#xff0c;块与块之间不能有数据重复的交集。块的数量一般等于数字个数开根号 核心思路&#xff…...

进制数知识(2)—— 浮点数在内存中的存储 和 易混淆的二进制知识总结

目录 1. 浮点数在内存中的存储 1.1 浮点数的大V表示法 1.2 浮点数的存储格式 1.3 浮点数的存入规则 1.4 浮点数的读取规则 1.5 补充&#xff1a;移码与掩码 1.6 题目解析 2. 易错的二进制知识 2.0 符号位到底会不会参与运算&#xff1f; 2.0.1 存储前的编码变化运算 …...

类似QQ聊天功能的Java程序

实现一个类似QQ聊天功能的Java程序需要考虑以下几个关键点&#xff1a; 用户界面&#xff1a;用于展示消息和输入消息。网络通信&#xff1a;用于客户端之间的信息传输。用户管理&#xff1a;用于管理用户的登录、注册和状态。消息存储&#xff1a;用于存储聊天记录。 这里提…...

Redis 键值对数据库学习

目录 一、介绍 二、安装以及连接 三、设置连接密码 四、连接报错 五、redis 操作字符串以及过期时间 六、 redis 列表操作 七、redis 集合操作 八、hash 哈希操作 九、redis 发布和订阅操作 十、RDB和AOF的两种数据持久化机制 十一、 其他机器连接redis 十二、 pyt…...

逆向推理+ChatGPT,让论文更具说服力

学境思源&#xff0c;一键生成论文初稿&#xff1a; AcademicIdeas - 学境思源AI论文写作 使用ChatGPT辅助“逆向推理”技巧&#xff0c;可以显著提升论文的质量和说服力。逆向推理从结论出发&#xff0c;倒推所需的证据和论点&#xff0c;确保整个论证过程逻辑严密且无漏洞。…...

「JavaScript深入」一文说明白JS的执行上下文与作用域

JavaScript深入 — 执行上下文与作用域 上下文执行上下文生命周期创建阶段执行阶段回收阶段 执行栈作用域链作用域词法作用域&#xff08;静态作用域&#xff09; 上下文 变量或函数的上下文决定了它们可以访问哪些数据&#xff0c;以及它们的行为。 每个上下文都有一个关联的…...

Qt C++设计模式->组合模式

组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;允许你将对象组合成树形结构以表示部分与整体的层次关系。组合模式使得客户端可以以统一的方式对待单个对象和组合对象&#xff0c;简化了对复杂树形结构的操作。 组合模式的应用场景 组合…...

Acwing Bellman-Ford SPFA

1. Bellman-Ford 该算法适用于有负权边的情况&#xff0c;注意&#xff1a;如果有负权环的话&#xff0c;最短路就不一定存在了。时间复杂度 O ( m n ) . O(mn). O(mn).该算法可以求出来图中是否存在负权回路&#xff0c;但求解负权回路&#xff0c;通常用SPFA算法&#xff0c…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...