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

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...