Count number of occurrences (or frequency) in a sorted array
Last Updated : 03 Oct, 2025
Given a sorted array arr[] and an integer target, find the number of occurrences of target in given array.
Examples:
Input: arr[] = [1, 1, 2, 2, 2, 2, 3], target = 2
Output: 4
Explanation: 2 occurs 4 times in the given array.
Input: arr[] = [1, 1, 2, 2, 2, 2, 3], target = 4
Output: 0
Explanation: 4 is not present in the given array.
[Naive Approach] Using Linear Search - O(n) Time and O(1) Space
The idea is to traverse the array and for each element, check if it is equal to the target. If you find any element equal to target increment the value of counter variable.
C++ #include <iostream> #include <vector> using namespace std; int countFreq(vector<int> &arr, int target) { int res = 0; for (int i = 0; i < arr.size(); i++) { // If the current element is equal to // target, increment the result if (arr[i] == target) res++; } return res; } int main() { vector<int> arr = {1, 1, 2, 2, 2, 2, 3}; int target = 2; cout<< countFreq(arr, target); return 0; } #include <stdio.h> int countFreq(int arr[], int n, int target) { int res = 0; for (int i = 0; i < n; i++) { // If the current element is equal to // target, increment the result if (arr[i] == target) res++; } return res; } int main() { int arr[] = {1, 1, 2, 2, 2, 2, 3}; int target = 2; int n = sizeof(arr) / sizeof(arr[0]); printf("%d", countFreq(arr, n, target)); return 0; } class GfG { static int countFreq(int[] arr, int target) { int res = 0; for (int i = 0; i < arr.length; i++) { // If the current element is equal to // target, increment the result if (arr[i] == target) res++; } return res; } public static void main(String[] args) { int[] arr = {1, 1, 2, 2, 2, 2, 3}; int target = 2; System.out.println(countFreq(arr, target)); } } # Python program to find the occurrence of given # target using linear search def countFreq(arr, target): res = 0 for i in range(len(arr)): # If the current element is equal to # target, increment the result if arr[i] == target: res += 1 return res if __name__ == "__main__": arr = [1, 1, 2, 2, 2, 2, 3] target = 2 print(countFreq(arr, target))
using System; class GfG { static int countFreq(int[] arr, int target) { int res = 0; for (int i = 0; i < arr.Length; i++) { // If the current element is equal to // target, increment the result if (arr[i] == target) res++; } return res; } static void Main(string[] args) { int[] arr = {1, 1, 2, 2, 2, 2, 3}; int target = 2; Console.WriteLine(countFreq(arr, target)); } } function countFreq(arr, target) { let res = 0; for (let i = 0; i < arr.length; i++) { // If the current element is equal to // target, increment the result if (arr[i] === target) res++; } return res; } // Driver Code const arr = [1, 1, 2, 2, 2, 2, 3]; const target = 2; console.log(countFreq(arr, target)); [Expected Approach] Using Binary Search - O(log n) Time and O(1) Space
Since the array is already sorted, we can use binary search to find the occurrences of a given target. First, we find the index of the first occurrence (Lower Bound) of target and then the index of the first element greater than the target (Upper Bound). The difference between these two indices will give the total number of occurrences of the target.
C++ #include <iostream> #include <vector> #include <algorithm> using namespace std; int countFreq(vector<int> &arr, int target) { int l = lower_bound(arr.begin(), arr.end(), target) - arr.begin(); int r = upper_bound(arr.begin(), arr.end(), target) - arr.begin(); // Return the differnce between upper // bound and lower bound of the target return r - l; } int main() { vector<int> arr = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8}; int target = 2; cout<< countFreq(arr, target); return 0; } #include <stdio.h> // Function to return Lower Bound int lowerBound(int arr[], int n, int target) { int res = n; // Search space for binary search int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] >= target) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } // Function to return Upper Bound int upperBound(int arr[], int n, int target) { int res = n; // Search space for binary search int lo = 0, hi = n - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] > target) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } int countFreq(int arr[], int n, int target) { // Return the difference between upper // bound and lower bound of the target return upperBound(arr, n, target) - lowerBound(arr, n, target); } int main() { int arr[] = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8}; int target = 2; int n = sizeof(arr) / sizeof(arr[0]); printf("%d\n", countFreq(arr, n, target)); return 0; } class GfG { // Function to return Lower Bound static int lowerBound(int[] arr, int target) { int res = arr.length; // Search space for binary search int lo = 0, hi = arr.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] >= target) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } // Function to return Upper Bound static int upperBound(int[] arr, int target) { int res = arr.length; // Search space for binary search int lo = 0, hi = arr.length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] > target) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } static int countFreq(int[] arr, int target) { // Return the difference between upper // bound and lower bound of the target return upperBound(arr, target) - lowerBound(arr, target); } public static void main(String[] args) { int[] arr = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8}; int target = 2; System.out.println(countFreq(arr, target)); } } from bisect import bisect_left, bisect_right # Function to find the occurrence of the given target # using binary search def countFreq(arr, target): l = bisect_left(arr, target) r = bisect_right(arr, target) # Return the difference between upper bound and # lower bound of the target return r - l if __name__ == "__main__": arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8] target = 2 print(countFreq(arr, target))
using System; class GfG { // Function to return Lower Bound static int lowerBound(int[] arr, int target) { int res = arr.Length; // Search space for binary search int lo = 0, hi = arr.Length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] >= target) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } // Function to return Upper Bound static int upperBound(int[] arr, int target) { int res = arr.Length; // Search space for binary search int lo = 0, hi = arr.Length - 1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] > target) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } static int countFreq(int[] arr, int target) { // Return the difference between upper // bound and lower bound of the target return upperBound(arr, target) - lowerBound(arr, target); } static void Main() { int[] arr = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8}; int target = 2; Console.WriteLine(countFreq(arr, target)); } } // Function to return Lower Bound function lowerBound(arr, target) { let res = arr.length; // Search space for binary search let lo = 0, hi = arr.length - 1; while (lo <= hi) { let mid = lo + Math.floor((hi - lo) / 2); if (arr[mid] >= target) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } // Function to return Upper Bound function upperBound(arr, target) { let res = arr.length; // Search space for binary search let lo = 0, hi = arr.length - 1; while (lo <= hi) { let mid = lo + Math.floor((hi - lo) / 2); if (arr[mid] > target) { res = mid; hi = mid - 1; } else { lo = mid + 1; } } return res; } function countFreq(arr, target) { // Return the difference between upper // bound and lower bound of the target return upperBound(arr, target) - lowerBound(arr, target); } // Driver Code const arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]; const target = 2; console.log(countFreq(arr, target));
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile