In this question, you’ll have to find the frequency of a given number(k) in a sorted array (nums[ ]). Below we have provided some of the examples so that you can have a better understanding of how to count occurrence in a sorted array.
Input: nums[] = {10, 10, 10, 20, 20, 30}
k = 20
Output: 2 // 20 appears twice in the given array
Input: nums[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4}
k = 4
Output: 4
Input: nums[] = {10, 10, 10, 10, 10}
k = 10
Output: 5
Input: nums[] = {5, 8, 10}
k = 7
Output: 0//since the number is not present in the arrayTable of Contents
Naive Solution(Using Linear Search)
In this approach, we use a linear search to get the count of every element present in the given array. Below we have written the C++ program to count occurrence in a sorted array.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//program to count occurrence in a sorted array
int countOccurrence(int nums[], int n, int k){ //function to count the occurrence of the k
int i, count=0;
for(i=0;i<n;i++){
if(nums[i]==k)
count++;//counting the occurrence in the given array
}
return count;//returning the frequency to the main function
}
int main(){
int nums[] = {1, 2, 2, 2, 2, 3};
int k = 2;
int n = sizeof(nums)/sizeof(nums[0]);
int count = countOccurrence(nums, n, k);//calling the function to count occurrence in a sorted array
cout<<count;
return 0;
}
Output
4Dry Run
Input: {1, 2, 2, 2, 2, 3} , k = 2
When i=0, count = 0
When i=1, count = 1
When i=2, count = 2
When i=3, count = 3
When i=4, count = 4
When i=5, count = 4Working of the code
In this solution, we just linearly traverse the array unless we find k in it. Once we reach the value, we keep on increasing the count till we iterate over the same value. If the element is not present in the array then the function will return the default value of the count variable. Although this is the simplest approach and will also work if the array is not sorted, the time complexity is O(N) which can be further improved using binary search.
Efficient Approach(Using Binary Search)
Since it is a sorted array, we must make use of the advantage provided. In this, we will create three functions to get the final solution. Below we have shown the C++ program to count occurrence in a sorted array using binary search.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//program to count occurrence in a sorted array using binary search
int firstOccurrence(int nums[], int n, int k){ //function to calculate the first occurrence of element
int low = 0, high = n-1;
while(low<=high){
int mid = (low+high)/2;
if(k<nums[mid])
high = mid-1;
else if(k>nums[mid])
low = mid+1;//till here it is the normal functioning of binary search
else{
if(mid==0 or nums[mid-1]!=nums[mid])//checking if it is the first occurrence
return mid;
else
high = mid-1;
}
}
return -1;//the function will return -1 when the element is not found
}
int lastOccurrence(int nums[], int n, int k){ //function to calculate the last occurrence of the element
int low = 0, high = n-1;
while(low<=high){
int mid = (low+high)/2;
if(k<nums[mid])
high = mid-1;
else if(k>nums[mid])
low = mid+1;
else{
if(mid==n-1 or nums[mid+1]!=nums[mid])//checking if it is the last occurrence
return mid;
else
low = mid+1;
}
}
return -1;//the function will return -1 when the element is not found
}
int countOccurrence(int nums[], int n, int k){//program to count the occurrence in a sorted array
int first = firstOccurrence(nums, n, k);
if(first == -1)
return 0;// i.e., if the element is not present the function will return 0
else
return(lastOccurrence(nums, n, k) - first + 1);
}
int main(){
int nums[] = {1, 2, 2, 3, 3, 3, 4, 4, 4, 4};
int k = 4;
int n = sizeof(nums)/sizeof(nums[0]);
int count = countOccurrence(nums, n, k);//calling the function to count occurrence in a sorted array
cout<<count;
return 0;
}
Output
4Working of the code
The solution works in 3 parts: First, we calculate the first occurrence using binary search and return the position if found else returns -1. Similarly in the second function, we calculate the last occurrence using binary search and return the position if found else returns -1. Using these positions we can easily find the frequency of the given element and if not found, the function returns 0. This is the most efficient method to solve this question and the time complexity of this method O(log(N)).
If you liked the article, here are some other article that you may like: Sieve of Eratosthenes and Window Sliding Technique – An Efficient Technique