首页/新闻资讯/正文详情

cpp算法题目整理——二分查找篇

发布时间:2026/11/21 1:20:23 来源:云帆数科 栏目:资讯中心
cpp算法题目整理——二分查找篇
寻找食物储量题目描述你是一个冒险家在一个危机四伏的森林里你发现了一个隐藏的食物仓库。这个食物仓库由 n 个房间组成每个房间都有一定数量的食物。你需要找到第一个房间其中的食物数量大于或等于一个给定的值 x。这些房间是按食物数量升序排列的。你知道每个房间的食物数量但由于时间紧迫你不能一个个房间地去查找。因此你决定使用二分搜索来快速找到目标房间。你的任务是编写一个程序根据每个房间的食物数量和目标值 x输出第一个食物数量大于或等于 x 的房间的编号。解题思路这个是标准二分查找模板题构建一个二分查找函数最终返回值要加1。#include iostream #include vector using namespace std; //二分查找函数 int binary_search(int n, int target, vectorint nums){ int l 0; int r n - 1; int ans -1; //当左右指针未重合时 不断缩小空间 while(l r){ //保守做法 绝对不会出现越界 int mid l (r - l) / 2; //满足条件 if(nums[mid] target){ //右指针左移 缩小空间 r mid - 1; //记录答案 ans mid; } //不满足条件 左指针替换为mid右侧 else{ l mid 1; } } return ans; } int main(){ int n, x; cin n; vectorint nums(n); for(int i 0; i n; i){ cin nums[i]; } cin x; int ans binary_search(n, x, nums); if(ans ! -1){ //输出房间号需要加1 cout ans 1 endl; } else{ cout -1 endl; } return 0; }二分查找题目描述给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果target存在返回下标否则返回-1。你必须编写一个具有O(log n)时间复杂度的算法。解题思路标准二分查找和上一题有所不同的是这个是要查询到相等的元素因此需要额外一个相等的分支来判断。class Solution { public: int search(vectorint nums, int target) { int l 0; int r nums.size() - 1; while(l r){ int mid l (r - l) / 2; //判断相等的情况 如果相等直接return就行 if(nums[mid] target){ return mid; } else if(nums[mid] target){ r mid - 1; } else{ l mid 1; } } //没找到相等的元素 返回-1 return -1; } };在排序数组中查找元素的第一个位置和最后一个位置题目描述给你一个按照非递减顺序排列的整数数组nums和一个目标值target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值target返回[-1, -1]。你必须设计并实现时间复杂度为O(log n)的算法解决此问题。解题思路这个题目要用到两次二分查找第一次查找左边界第二次查找右边界因此我写了一个函数用来查找两个边界这里return l和return r 1是完全等价的因为循环终止的条件就是l r此时只能是l r 1然后将target 1这样就可以找到右边界。class Solution { public: // 基础二分寻找第一个 target 的下标 int lower_bound(vectorint nums, int target) { int l 0, r nums.size() - 1; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) { r mid - 1; } else { l mid 1; } } return l; } vectorint searchRange(vectorint nums, int target) { //左界限start int start lower_bound(nums, target); // 如果越界或者找到的数根本不是 target说明 target 不存在 if (start nums.size() || nums[start] ! target) { return {-1, -1}; } // 找 target 1 的左边界减 1 就是 target 的右边界 int end lower_bound(nums, target 1) - 1; return {start, end}; } };

相关推荐

在 Claude Code、Cursor 里读小红书和抖音链接:MCP 配置、五个工具和排错(附真实返回)
在 Claude Code、Cursor 里读小红书和抖音链接:MCP 配置、五个工具和排错(附真实返回)

声明:文中的 LinkDigest 是作者本人开发的服务。下面的配置和返回都来自真实运行,只做了删节。问题:AI 打不开小红书、抖音链接 在 Claude Code 或 Cursor 里贴一条小红书笔记、抖音视频的链接,让它「总结一下」,常见的… · 2026/11/14 3:31:24

Linux 软件包管理与服务控制:apt、源码编译与 systemd 实战
Linux 软件包管理与服务控制:apt、源码编译与 systemd 实战

软件包管理与服务控制:apt、源码编译与 systemd 一篇讲透运维学习路线系列 阶段一 Linux 地基 第 5 篇 适用环境:Ubuntu 24.04 LTS(附 CentOS Stream 9 的 dnf 对照),普通用户(有 sudo) 阅读前… · 2026/11/20 23:58:47

Zephyr移植精英板第十五章 按键输入实验
Zephyr移植精英板第十五章 按键输入实验

思路依然是看说明文档和例程,本文仅提供参考,务必自己从翻文档开始,自己完成实验结果。一、新建新工程参考下图指令复制上一个工程到lab_3,中间build 报错,因为没清除上一个工程的build,清除掉重编译即可。… · 2026/11/19 20:09:35

低压电工证钢管行业前景与薪资待遇,全国通用怎么考不白交培训费
低压电工证钢管行业前景与薪资待遇,全国通用怎么考不白交培训费

低压电工证钢管行业前景与薪资待遇,全国通用怎么考不白交培训费 怕考不过白交培训费?低压电工证钢管行业门槛高、风险大,考个全国通用的证是第一步。很多人因为不了解流程,结果花了钱还没证,白白浪费时间和金钱。今天就从新乡初次报考者的角度,一步步告… · 2026/11/21 1:20:05

清徐电工证复审培训:学历不高怕报不上名?2026河南最新政策这样应对
清徐电工证复审培训:学历不高怕报不上名?2026河南最新政策这样应对

清徐电工证复审培训:学历不高怕报不上名?2026河南最新政策这样应对 学历不高怕报不上名?其实清徐电工证复审培训没有那么难,关键是你怎么准备。2026河南最新政策已经明确,只要满足基本条件,就能顺利报考和复审。别再被学历门槛吓退了,下面我就… · 2026/11/21 1:20:05

南乐县电工证报名千万别踩坑,怕考不过白交培训费怎么破?
南乐县电工证报名千万别踩坑,怕考不过白交培训费怎么破?

南乐县电工证报名千万别踩坑,怕考不过白交培训费怎么破? 你是不是也听说过“电工证一证在手,天下我有”?可现实是,很多人花了几千块报名,结果考试没过、培训没用,钱花了,证没拿到,还得重新来一遍。 怕考不过白交培训费… · 2026/11/21 1:20:05

电工证考试实用资料有效期多久 官方回应来了
电工证考试实用资料有效期多久 官方回应来了

电工证考试实用资料有效期多久 官方回应来了 工地太忙根本没时间复习考试,这是很多一线工人的真实写照。尤其是像电工证这种需要频繁复审的特种作业证书,很多人压根不知道具体的有效期和官方政策。最近在河南政务服务网上,就有人问过“电工证考试实用资料… · 2026/11/21 1:20:05

电工证报名有保障么?值不值得考?别再交冤枉钱了
电工证报名有保障么?值不值得考?别再交冤枉钱了

电工证报名有保障么?值不值得考?别再交冤枉钱了 怕考不过白交培训费?别慌,先看完这篇!现在电工证报名有保障么?值不值得考?这些问题困扰着不少想进工地、进厂、进工地的小伙伴。特别是像我们濮阳公路工程从业者,很多人一上来就被培训机构“忽悠”交钱… · 2026/11/21 1:20:05

厨房维修电工证怎么考?含金量到底有多高?周口施工老板必看
厨房维修电工证怎么考?含金量到底有多高?周口施工老板必看

厨房维修电工证怎么考?含金量到底有多高?周口施工老板必看 你是不是也在为“厨房维修电工证怎么考”发愁?报名渠道不清楚,怕被中介坑,怕钱花了证办不下来?这种焦虑我懂,我自己在周口做施工管理时也遇到过,找了个“包过”的中介,结果花了两三千,证还… · 2026/11/21 1:19:05

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/20 16:18:19

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/20 18:25:07

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/20 17:56:32

电工证征求意见2026河南最新政策怎么应对?学历不高也能考!
电工证征求意见2026河南最新政策怎么应对?学历不高也能考!

电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 你是不是也担心自己学历不高, 怕报不上名 ?尤其是像焦作水利工程这样的从业者,常年在一线作业,但证书却成了晋升、转岗、接项目的关键门槛。 2026河南最新政策… · 2026/11/21 0:00:17

电工证征求意见怎么填?含金量高不高?济源电工朋友看过来
电工证征求意见怎么填?含金量高不高?济源电工朋友看过来

电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 不知道去哪报名怕被中介坑,电工证征求意见填错了不仅白费钱,还可能影响后续考试和工作。最近很多济源的电工朋友都在问: 电工证征求意见怎么填… · 2026/11/21 0:00:17

房建企业特种工考前押题怎么找?别让培训费打了水漂
房建企业特种工考前押题怎么找?别让培训费打了水漂

房建企业特种工考前押题怎么找?别让培训费打了水漂 怕考不过白交培训费?房建企业特种工考试难度高、题型多,很多人报名后才发现没有合适的复习资料,最终考试落榜,白白浪费了时间和金钱。别担心,掌握【考前押题】的技巧,能让你事半功倍,顺利通过考试。… · 2026/11/21 0:00:17

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:45

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:54

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:26:03

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码