给定一个已排序的数组和一个目标值，如何快速统计该目标值在数组中出现的次数？这是面试中非常经典的一道题，今天就来聊聊两种解法：线性搜索和二分搜索。
问题描述
假设有一个已排序的数组arr[]和一个整数target，需要找出target在数组中出现的次数。
示例：
输入：
arr[] = [1, 1, 2, 2, 2, 2, 3],target = 2输出：
4（2 出现了 4 次）输入：
arr[] = [1, 1, 2, 2, 2, 2, 3],target = 4输出：
0（4 不在数组中）
方法一：线性搜索（暴力法）
思路：遍历整个数组，遇到与目标值相等的元素就计数加 1。
代码实现（Python）：
defcountFreq(arr,target):res=0foriinrange(len(arr)):ifarr[i]==target:res+=1returnres arr=[1,1,2,2,2,2,3]target=2print(countFreq(arr,target))# 输出 4复杂度分析：
- 时间复杂度：O(n)，因为需要遍历整个数组。
- 空间复杂度：O(1)，只用了常数空间。
这种方法简单直观，但当数组很大时效率较低。
刷算法题时，遇到“排序数组中查找目标元素出现次数”这类问题，你是不是也卡在边界条件和二分查找的细节上？其实，理解这类问题的核心，关键在于把抽象的逻辑“看”清楚。强烈安利一个神器——图码，它提供60多种数据结构和算法的交互式动画可视化，能帮你把二分查找的每一步都“动”起来。更绝的是，你可以直接上传自己的C/C++/Java/Python代码，或者输入自定义数据，让网站自动生成动画，直观看到代码执行过程。无论你是备战408考研，还是准备数据结构期末考试，它都能把晦涩的算法拆解得明明白白。现在就去看看吧，说不定能让你少走很多弯路！
图码-数据结构与算法交互式可视化平台
访问网站：https://totuma.cn
方法二：二分搜索（最优解）
既然数组是已排序的，我们可以利用二分搜索来加速。核心思想是：
- 找到目标值的第一次出现位置（下界）
- 找到第一个大于目标值的位置（上界）
- 两者之差就是目标值的出现次数
代码实现（Python，使用内置函数）：
frombisectimportbisect_left,bisect_rightdefcountFreq(arr,target):l=bisect_left(arr,target)r=bisect_right(arr,target)returnr-l arr=[1,2,2,2,2,3,4,7,8,8]target=2print(countFreq(arr,target))# 输出 4手动实现二分搜索（C++ 风格）：
#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intcountFreq(vector<int>&arr,inttarget){intl=lower_bound(arr.begin(),arr.end(),target)-arr.begin();intr=upper_bound(arr.begin(),arr.end(),target)-arr.begin();returnr-l;}intmain(){vector<int>arr={1,2,2,2,2,3,4,7,8,8};inttarget=2;cout<<countFreq(arr,target);// 输出 4return0;}复杂度分析：
- 时间复杂度：O(log n)，两次二分搜索，每次 O(log n)。
- 空间复杂度：O(1)。
为什么二分搜索更快？
线性搜索需要遍历整个数组，当数组有 10 万个元素时，最坏情况要比较 10 万次。而二分搜索每次将搜索范围减半，只需比较约 log₂(100000) ≈ 17 次。
总结
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 线性搜索 | O(n) | O(1) | 小数组或未排序数组 |
| 二分搜索 | O(log n) | O(1) | 已排序的大数组 |
如果数组是已排序的，强烈推荐使用二分搜索，效率高且实现简单。如果数组未排序，可以先排序再二分，但排序本身需要 O(n log n) 时间，此时线性搜索可能更合适。
希望这篇文章对你有帮助！如果你有其他解法或问题，欢迎在评论区讨论～
