InterviewGuide 剑指 Offer 刷题笔记：No37 统计一个数字在升序数组中出现的次数（二分查找模板详解）-北京尧图网络

文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本篇是 InterviewGuide 仓库「带你快速刷完67道剑指 Offer」专栏中No37「统计一个数字在排序数组中出现的次数」的完整题解。这道题是数组类二分查找的高频考点本篇文章将从题目本身出发给出基于 C 标准库equal_range的取巧写法与纯手写二分查找的标准模板并补充复杂度分析、边界情况与扩展思路。读完本篇你将掌握在有序数组中定位某个值的左边界与右边界这一经典能力并能在面试手撕环节快速写出无死角的二分代码。题目描述统计一个数字在升序数组中出现的次数。这是《剑指 Offer》中的经典面试题专栏导读中注明题目均出自《何海涛. 剑指 Offer[M]. 电子工业出版社, 2012.》也是面试中高频考察的手撕算法题目之一参见面试高频算法真题中对笔试、面试算法难度分布的说明。示例 1输入[1,2,3,3,3,3,4,5],3返回值4即数组[1, 2, 3, 3, 3, 3, 4, 5]中数字3一共出现了 4 次。关键前提数组是升序排列的。如果数组无序本问题的解法就要另当别论正因为有序我们才能利用二分查找把时间复杂度降到O(log n)而不是老老实实遍历一遍数组。解法一STL 取巧写法直接调用 equal_range()如果面试环境允许使用 C 标准库最简单直接的做法是利用algorithm头文件中的std::equal_rangeint GetNumberOfK(vectorint data, int k) { auto pos equal_range(data.begin(), data.end(), k); return pos.second - pos.first; }原理说明std::equal_range要求序列已按排序升序它对一个有序区间调用两次二分查找lower_bound找到第一个大于等于k的元素位置upper_bound找到第一个大于k的元素位置两者之差pos.second - pos.first恰好就是k在区间内出现的次数。返回值类型是std::pairiterator, iterator两个迭代器相减得到difference_type正好可以隐式转换为int返回。适用场景与局限这是记 API 即可的写法代码极短、不易出错适合对标准库熟悉的同学快速作答但面试官很可能要求手写二分查找来考察你对二分边界条件的掌握程度因此解法二才是真正的核心。解法二手写二分找到第一次出现和最后一次出现的位置本题更标准的做法是两次二分分别找到k第一次出现的位置和最后一次出现的位置两者之差加 1 即为出现次数。阿秀在 37-剑指offer.md 中给出的二分模板如下牛客网实测运行时间 2ms占用内存 504kint GetNumberOfK(vectorint data, int k) { int low 0, high data.size() - 1; if (high -1) return 0; // data 为空 while (low high) { int mid low (high - low) / 2; if (data[mid] k) high mid - 1; else if (data[mid] k) low mid 1; else { // 已经找到 k 的一个位置 mid int count 0; count; // 先计入 data[mid] 本身 int index mid - 1; while (index 0 data[index] k) { // 向左扩展 count; index--; } index mid 1; while (index data.size() - 1 data[index] k) { // 向右扩展 count; index; } return count; } } return 0; // 没有找到直接返回 0 }核心模板口诀阿秀原话low highlow mid 1high mid - 1逐段拆解空数组保护high data.size() - 1当data为空时high -1直接返回 0避免后续对data[mid]的越界访问二分主循环while (low high)是标准闭区间写法。mid low (high - low) / 2等价于(low high) / 2但避免了low high溢出是工程上推荐的写法三分支判断data[mid] k目标在左半区间high mid - 1data[mid] k目标在右半区间low mid 1data[mid] k找到了一个位置接下来向左右两侧线性扩展统计左右扩展计数以mid为中心向左扫描所有等于k的元素data[index] k向右扫描同理。注意两个 while 循环都先判断下标边界index 0、index data.size() - 1再访问数组防止越界未命中兜底循环结束仍没找到k返回 0。为什么推荐记住这种写法这道题的本质是在有序数组中查找重复元素的区间。相比先遍历一遍计数的O(n)朴素解法二分法在数据量很大时优势明显。而相比直接背lower_bound/upper_bound的实现这种先二分命中再线性扩展的写法思路直观、边界清晰遇到面试官追问时更容易自圆其说。仓库 03-leetcode/06-二分查找目录下收集了大量二分查找专题题目如 704.二分查找、278.第一个错误的版本等可以用于巩固这个模板。复杂度与边界分析解法时间复杂度空间复杂度说明朴素遍历O(n)O(1)直接 count最简单但面试通常不会满意解法一equal_rangeO(log n)O(1)两次二分标准库实现解法二二分扩展平均O(log n)最坏O(n)O(1)当k在数组中大量重复时线性扩展可能退化为O(n)说明解法二在最坏情况下例如整个数组全部等于k左右扩展会遍历整个数组时间复杂度退化为O(n)。若希望严格保持O(log n)可以改为两次独立的二分分别求左边界与右边界即手写lower_bound与upper_bound这也是对解法二的自然延伸可在面试中作为加分项提及。需要重点自测的边界情况空数组[]→ 返回 0数组中不存在k→ 返回 0k出现在数组首尾如[3,3,4,5]查3[1,2,3,3]查3→ 检查左右扩展的越界保护数组元素全部等于k→ 检查扩展逻辑不会漏数。扩展同一思路的多语言迁移虽然专栏以 C 实现为主但二分求左右边界的思路完全可以用其他语言复刻Java可用Arrays.binarySearch定位一个位置后向两侧扩展或手写lowerBound/upperBoundArrays.binarySearch在未命中时返回负数插入点需额外处理Python标准库bisect模块提供bisect_left与bisect_right两者之差即为出现次数与 C 的lower_bound/upper_bound一一对应Golang标准库sort.SearchInts返回第一个大于等于目标的位置配合手写右边界查找即可完成。仓库中 Java、Golang、Python 三个目录是各语言知识点的汇总入口可以结合自身求职语言继续补充。小结本题作为剑指 Offer 第 37 题考察的核心能力点有三个识别有序数组这个关键前提从而想到二分查找掌握闭区间二分模板low high、low mid 1、high mid - 1能正确处理边界把统计出现次数转化为求值区间无论是用标准库equal_range还是手写左右扩展都要能讲清楚原理与复杂度。完整的 67 道剑指 Offer 题解可在剑指offer全集.md 中一次性查看本题位于该文件第 4476 行附近单题版本见 37-剑指offer.md。如果你刚开始刷题建议先阅读 01-basic-algorithm/02-algorithm-basic.md 掌握排序、时间/空间复杂度等基础概念再按专栏顺序逐题攻克。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐剑指 Offer 第 1 题详解二维数组中的查找——右上角逼近法与逐行二分法InterviewGuide 刷题笔记剑指 Offer 第 1 题详解二维数组中的查找——右上角逼近法与逐行二分法InterviewGuide 刷题笔记本文基于 InterviewGuide文档教程知识库剑指 Offer 56-II 数组中数字出现的次数 II用有限状态机与位统计在 O(1) 空间找出只出现一次的数字剑指 Offer 56 II 数组中数字出现的次数 II用有限状态机与位统计在 O 1 空间找出只出现一次的数字本文基于 LeetCode Book 仓库中示例工程InterviewGuide 剑指Offer No28「数组中出现次数超过一半的数字」哈希计数与摩尔投票法双解法详解InterviewGuide 剑指Offer No28「数组中出现次数超过一半的数字」哈希计数与摩尔投票法双解法详解本文围绕 InterviewGuide文档教程知识库上一篇解决TranslucentTB启动失败从根源排查到完美修复下一篇如何快速掌握Scikit-learn机器学习基于python-guide的完整入门教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

InterviewGuide 剑指 Offer 刷题笔记：No37 统计一个数字在升序数组中出现的次数（二分查找模板详解）

相关推荐

布拉格微环与二维材料集成：从仿真到流片的硅光实战经验

可持续架构决策实践指南：基于 architecture-decision-record 仓库的八条落地法则

Ant Design Blazor 的 Select 下拉框样式定制：ListboxStyle 属性深入实战

更多资讯

短视频配音工具哪个好用

微信自动回复突然全停了？五个检查点从外到内

影刀RPA数字员工入门：从零搭建自动化流程实战手册

BLE SMP 抓包实战

v-charts 高级属性实战：extend 配置扩展、afterConfig 钩子与加载/空数据状态管理

Semantic Router Adaptation 在线模型选择学习机制详解：配置、评分算法与可观测性

今日更新

Susi AI API实战指南：susi_alexa_skill如何用Node.js调用chat.json获取智能回答

换新电脑了？KeyStats 恢复码数据找回完全指南，端到端加密统计一键重建

重建二叉树：由前序与中序遍历序列还原二叉树的原理与 Java 实现（YCBlogs 剑指 Offer 精讲）

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？