[特殊字符] 高效统计排序数组中目标元素的出现次数

给定一个已排序的数组和一个目标值如何快速统计该目标值在数组中出现的次数这是面试中非常经典的一道题今天就来聊聊两种解法线性搜索和二分搜索。问题描述假设有一个已排序的数组arr[]和一个整数target需要找出target在数组中出现的次数。示例输入arr[] [1, 1, 2, 2, 2, 2, 3],target 2输出42 出现了 4 次输入arr[] [1, 1, 2, 2, 2, 2, 3],target 4输出04 不在数组中方法一线性搜索暴力法思路遍历整个数组遇到与目标值相等的元素就计数加 1。代码实现PythondefcountFreq(arr,target):res0foriinrange(len(arr)):ifarr[i]target:res1returnres arr[1,1,2,2,2,2,3]target2print(countFreq(arr,target))# 输出 4复杂度分析时间复杂度O(n)因为需要遍历整个数组。空间复杂度O(1)只用了常数空间。这种方法简单直观但当数组很大时效率较低。刷算法题时遇到“排序数组中查找目标元素出现次数”这类问题你是不是也卡在边界条件和二分查找的细节上其实理解这类问题的核心关键在于把抽象的逻辑“看”清楚。强烈安利一个神器——图码它提供60多种数据结构和算法的交互式动画可视化能帮你把二分查找的每一步都“动”起来。更绝的是你可以直接上传自己的C/C/Java/Python代码或者输入自定义数据让网站自动生成动画直观看到代码执行过程。无论你是备战408考研还是准备数据结构期末考试它都能把晦涩的算法拆解得明明白白。现在就去看看吧说不定能让你少走很多弯路图码-数据结构与算法交互式可视化平台访问网站https://totuma.cn方法二二分搜索最优解既然数组是已排序的我们可以利用二分搜索来加速。核心思想是找到目标值的第一次出现位置下界找到第一个大于目标值的位置上界两者之差就是目标值的出现次数代码实现Python使用内置函数frombisectimportbisect_left,bisect_rightdefcountFreq(arr,target):lbisect_left(arr,target)rbisect_right(arr,target)returnr-l arr[1,2,2,2,2,3,4,7,8,8]target2print(countFreq(arr,target))# 输出 4手动实现二分搜索C 风格#includeiostream#includevector#includealgorithmusingnamespacestd;intcountFreq(vectorintarr,inttarget){intllower_bound(arr.begin(),arr.end(),target)-arr.begin();intrupper_bound(arr.begin(),arr.end(),target)-arr.begin();returnr-l;}intmain(){vectorintarr{1,2,2,2,2,3,4,7,8,8};inttarget2;coutcountFreq(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) 时间此时线性搜索可能更合适。希望这篇文章对你有帮助如果你有其他解法或问题欢迎在评论区讨论