示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文围绕《剑指 Offer第 2 版》面试题 53-I「在排序数组中查找数字 I」展开该题是 doocs/leetcode 开源仓库中lcof系列的一道经典二分查找入门题。文章将完整讲解题目约束、二分边界推导过程、8 种语言的官方题解实现并结合仓库中的二分查找模板与主站 34 题进行对比深化读完即可掌握用两次 lower_bound 求区间长度这一可复用的高频套路。题目概述题目描述统计一个数字在排序数组中出现的次数。示例 1输入: nums [5,7,7,8,8,10], target 8 输出: 2示例 2输入: nums [5,7,7,8,8,10], target 6 输出: 0数据约束0 nums.length 10^5-10^9 nums[i] 10^9nums是一个非递减数组允许重复元素-10^9 target 10^9与主站 34 题的关系原文档明确指出本题与主站 34 题相同仅返回值不同。仓库中主站题解位于 0034.Find First and Last Position of Element in Sorted Array两道题的核心都是在有序数组中定位目标值的连续区间区别在于 34 题要求返回区间的左右端点[l, r]而本题只要求返回区间长度出现次数。在 lcof/README.md 的题解列表中本题被标记为标签数组、二分查找难度为「简单」适合作为二分查找边界类题目的入门训练。思路分析为什么不能线性扫描最直观的做法是遍历整个数组计数时间复杂度为 $O(n)$。但在 $n \le 10^5$ 且数组有序的前提下这种做法没有利用有序这一关键性质——这正是面试官期望你优化的点。二分查找的核心洞察在于target在有序数组中的出现区间是连续的。设该区间为[l, r)左闭右开其中l是第一个不小于target的位置r是第一个大于target的位置那么target的出现次数就是r - l。也就是说统计出现次数可以转化为两次边界二分第一次二分找到第一个 target的下标l即lower_bound第二次二分找到第一个 target的下标r即upper_bound等价于对target 1再做一次lower_bound答案 r - l。当target不存在时l与r指向同一位置r - l 0恰好符合示例 2 的输出无需额外判断。二分边界模板支撑仓库中的 basic/searching/BinarySearch/README.md 系统总结了二分查找的边界本质与两套模板二分的本质并非单调性而是边界。只要找到某种性质使得整个区间一分为二那么就可以用二分把边界点二分出来。其中模板 1查找左边界即第一个满足check(x)的位置与本题的lower_bound逻辑完全对应int search(int left, int right) { while (left right) { int mid left ((right - left) 1); if (check(mid)) { right mid; } else { left mid 1; } } return left; }该模板的关键细节循环条件为left right结束时left right正好落在答案位置中点使用差值计算left ((right - left) 1)避免left right溢出判定成立时收缩右边界right mid否则推进左边界left mid 1——这种写法保证答案始终位于二分区间内且天然支持无解时返回插入位置即lower_bound语义。仓库中还给出了模板 2查找右边界其区别在于mid计算需要补上奇数余数((right - left) 1)并在判定成立时left mid、否则right mid - 1。理解两套模板的差异是写对边界二分的基础。各语言实现详解原文档提供了 8 种语言的完整实现仓库中对应的可运行源码位于 lcof/面试题53 - I. 在排序数组中查找数字 I 目录下Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.rs、Solution.js、Solution.cs、Solution.swift。Python3class Solution: def search(self, nums: List[int], target: int) - int: l bisect_left(nums, target) r bisect_right(nums, target) return r - lPython 的bisect标准库直接提供了两种边界查找bisect_left返回第一个 target的位置左边界bisect_right返回第一个 target的位置右边界两者之差即出现次数。Javaclass Solution { private int[] nums; public int search(int[] nums, int target) { this.nums nums; int l search(target); int r search(target 1); return r - l; } private int search(int x) { int l 0, r nums.length; while (l r) { int mid (l r) 1; if (nums[mid] x) { r mid; } else { l mid 1; } } return l; } }Java 实现复用同一个search(x)函数返回第一个 x的位置先查target得到左边界l再查target 1得到右边界r。注意中点计算使用无符号右移(l r) 1防止大数组下l r溢出搜索区间为[0, nums.length]保证当target大于所有元素时返回nums.length这一合法越界下标。Cclass Solution { public: int search(vectorint nums, int target) { auto l lower_bound(nums.begin(), nums.end(), target); auto r upper_bound(nums.begin(), nums.end(), target); return r - l; } };C 标准库algorithm中lower_bound与upper_bound分别对应左、右边界返回迭代器二者相减std::distance语义即元素个数。这是标准库封装最直接的一种写法。Gofunc search(nums []int, target int) int { l : sort.SearchInts(nums, target) r : sort.SearchInts(nums, target1) return r - l }Go 标准库sort.SearchInts(a, x)返回a中第一个 x的索引等价于lower_bound因此右边界通过对target1再查一次得到无需手写二分循环。Rustimpl Solution { pub fn search(nums: Veci32, target: i32) - i32 { let search |x| { let mut l 0; let mut r nums.len(); while l r { let mid l (r - l) / 2; if nums[mid] x { r mid; } else { l mid 1; } } l as i32 }; search(target 1) - search(target) } }Rust 版本以闭包search封装下界查找使用l (r - l) / 2计算中点避免溢出两次调用后search(target 1) - search(target)即答案。JavaScript/** * param {number[]} nums * param {number} target * return {number} */ var search function (nums, target) { const search x { let l 0; let r nums.length; while (l r) { const mid (l r) 1; if (nums[mid] x) { r mid; } else { l mid 1; } } return l; }; const l search(target); const r search(target 1); return r - l; };JavaScript 用位运算(l r) 1求中点数组长度上限 $10^5$不会出现溢出问题内部search闭包与 Java 版逻辑一致。C#public class Solution { public int Search(int[] nums, int target) { int l search(nums, target); int r search(nums, target 1); return r - l; } private int search(int[] nums, int x) { int l 0, r nums.Length; while (l r) { int mid (l r) 1; if (nums[mid] x) { r mid; } else { l mid 1; } } return l; } }C# 实现与 Java 版本同构search(nums, x)返回第一个 x的下标主方法两次调用求差。Swiftclass Solution { private var nums: [Int] [] func search(_ nums: [Int], _ target: Int) - Int { self.nums nums let leftIndex search(target) let rightIndex search(target 1) return rightIndex - leftIndex } private func search(_ x: Int) - Int { var left 0 var right nums.count while left right { let mid (left right) / 2 if nums[mid] x { right mid } else { left mid 1 } } return left } }Swift 用成员变量缓存nums同样以对target和target1各做一次下界二分的方式求区间长度。复杂度分析时间复杂度$O(\log n)$。每次二分查找将搜索区间减半两次二分共 $O(\log n)$ 次比较其中 $n$ 为数组长度约束上限 $10^5$。空间复杂度$O(1)$。除若干指针/索引变量外无额外空间开销。相比线性扫描的 $O(n)$二分方案在大数组上具有明显优势这也正是本题的核心考点。边界情况与易错点target不存在此时两次下界查找返回同一位置r - l 0符合题目语义示例 2无需额外分支。空数组nums.length 0时两次查找都返回0结果为0代码天然正确。target位于数组边界小于所有元素l 0r 0结果0大于所有元素l r n结果0返回下标n属于合法越界哨兵用于差值计算不会出错。target 1的溢出风险Java、Go、C#、Swift 等版本通过search(target 1)实现upper_bound。题目约束-10^9 target 10^9远未触及 32 位整数上限因此target 1不会溢出若脱离该约束使用此技巧需要留意该前提。中点计算防溢出Java 使用(l r) 1、Rust 使用l (r - l) / 2均是对大数组防溢出的标准写法。与主站 34 题的对照主站 34. 在排序数组中查找元素的第一个和最后一个位置 与本题共享同一套解法骨架可对照学习34 题同样做两次下界查找l lower_bound(target)r lower_bound(target 1)34 题需返回区间端点因此要显式判断l r说明target不存在时返回[-1, -1]否则返回[l, r - 1]本题只需计数直接返回r - l天然覆盖不存在即 0的语义。两者的差异恰好演示了同一算法在不同返回值需求下的两种收尾写法判断边界 vs 直接求差。掌握这一对照即可把本题的解法推广到有序数组区间统计一类问题。总结本题是二分查找边界类问题的典型范例核心套路可归纳为三步识别有序数组 统计目标值区间 → 转化为两次lower_bound左边界查target右边界对target 1查lower_bound或直接使用语言的upper_bound出现次数 r - l时间复杂度 $O(\log n)$空间复杂度 $O(1)$。仓库 doocs/leetcode 在本目录下提供了 8 种语言的完整可运行源码Solution.py 等配合 二分查找模板 与 主站 34 题题解 一起研读即可完整掌握从模板到实战的二分边界写法。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐LeetCode-Book 剑指 Offer 53-I在排序数组中查找数字 I —— 双边界二分与插入点二分的完整解析LeetCode Book 剑指 Offer 53 I在排序数组中查找数字 I —— 双边界二分与插入点二分的完整解析 在 LeetCode Book 仓库的示例工程教程教育剑指 Offer No37统计一个数字在排序数组中出现的次数C 二分查找与 STL 解法详解剑指 Offer No37统计一个数字在排序数组中出现的次数C 二分查找与 STL 解法详解 本篇技术笔记围绕《剑指 Offer》第 37 题展开给教程YCBlogs 算法实战改进二分查找——统计数字在排序数组中出现的次数YCBlogs 算法实战改进二分查找——统计数字在排序数组中出现的次数 本篇基于 YCBlogs 算法笔记中《 在排序数组中出现的次数 https://lin教程技术博客文档上一篇用 Czkawka 免费找回 10GB 磁盘空间从重复文件到空目录的清理实操指南下一篇3秒锁定视频语言VideoLingo 自动语言检测机制完整拆解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考