Program to Count Occurrence in a Sorted Array (From Naive to an Efficient Approach)

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 array

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

4

Dry 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 = 4

Working 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

4

Working 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

Leave a Reply

Your email address will not be published. Required fields are marked *