New update is available. Click here to update.

Count the number of occurrences in a sorted Array

Jahanvi gulati
Last Updated: May 13, 2022
EASY

Introduction  

In this blog, we are going to discuss a very interesting problem. We are given an array of integers sorted in increasing order and a value and we are required to find the number of occurrences of the value in the given array. 

Let us go through some sample examples to understand the problem statement.

Sample Examples

Example 1:

Input: array[]={3,3,5,6,6,6,7,8}, x=6
Output:3

Explanation: The total number of occurrences of 6 is equal to 3.

 

Example 2:

Input: array[]={4,5,7,10,10,13,13,20}, x=6
Output: 0

Explanation: The total number of occurrences of 6 is equal to 0.

Approach to finding the number of occurrences(using linear search)

The process to find the number of occurrences is simple.

  • First, we declare an array of integer, which is sorted
  • Then we calculate the size of the array and declare a variable to store the value of occurrence of x.
  • Then using for loop, we check x at each place of the array, and if it is there, we increase the variable by 1.
  • And then return the value.

Implementation in C++

#include<iostream>
using namespace std;
 
int countOccurrences(int a[], int n, int x)
{
    int res = 0;
    for (int i=0; i<n; i++)
        if (x == a[i])
          res++;
    return res;
}
 
// Driver code
int main()
{
    int a[] = {5,66,9,10,10,76,89,100,100};
    int n = sizeof(a)/sizeof(a[0]);
    int x = 10;
    cout << countOccurrences(a, n, x);
    return 0;
}

 

Output:

2

 

Complexity Analysis

Time complexity: O(n)

space complexity:O(n)

 

Approach to finding the number of occurrences(using binary search)

We can use binary search to find the number of occurrences in a sorted array.This is a better approach and a very common application of binary search.

Implementation in C++

#include<iostream>
using namespace std;

int binarySearch(int a[], int l, int r, int x)
{
    if (r < l)
        return -1;
 
    int mid = l + (r - l) / 2;
 
    if (a[mid] == x)
        return mid;

    if (a[mid] > x)
        return binarySearch(a, l, mid - 1, x);

    return binarySearch(a, mid + 1, r, x);
}
 
int countOccurrences(int a[], int n, int x)
{
    int ind = binarySearch(a, 0, n - 1, x);

    if (ind == -1)
        return 0;

    int count = 1;
    int left = ind - 1;
    while (left >= 0 && a[left] == x)
        count++, left--;
 
    int right = ind + 1;
    while (right < n && a[right] == x)
        count++, right++;
 
    return count;
}
 
// Driver code
int main()
{
    int a[] = { 4,5,6,6,9,9,11,11,11,13,13};
    int n = sizeof(a) / sizeof(a[0]);
    int x = 11;
    cout << countOccurrences(a, n, x);
    return 0;
}

 

Output:

3

 

Complexity Analysis

Time complexity: O(log n+count)

Space complexity: O(n)

Approach to finding the number of occurrences(using improved binary search)

This is the best approach to find the number of occurrences.The approach to this method is simple:

  • In this method, first we will get the index of the first occurrence of the number in array[] using binary search.Let its index be x.
  • Now we will find the index of last occurrence of the number in array[]  using binary search method.Let this be denoted by y
  • So number of occurrences will be y-x+1.

Implementation in C++

# include <bits/stdc++.h>
using namespace std;
 
int count(int a[], int x, int n)
{   
  int *low = lower_bound(a, a+n, x);
 
  if (low == (a + n) || *low != x)
     return 0;
    
  int *high = upper_bound(low, a+n, x);    

  return high - low;
}


int main()
{
  int a[] = {2,5,6,6,7,8,9,9,9,10,11};
  int x =  9;  
  int n = sizeof(a)/sizeof(a[0]);
  int c = count(a, x, n);
  cout<<x<<" occurs "<<c <<" times in the array"<<endl;
  return 0;
}

 

Output:

9 occurs 3 times in the array

 

Complexity Analysis

Time complexity: O(log n)

Space complexity:O(n)

Frequently Asked Questions

  1. What is sizeof() function in c++?
    It is a function that returns the size of a data type like an array, expression, etc., in c++.for an array, it will return the number of elements in that array.
     
  2. Name some sorting techniques used in c++?
    Some of the most used sorting techniques are:
    → Bubble sort
    → Selection sort 
    → Quick sort
    → Merge sort
    → Heap sort
    → Shell sort
    → Insertion sort
     
  3. What is a class in c++?
    A class defines a datatype, and provide set of operations, and databits.Its is also used in c language .

Conclusion

In this blog, we discussed how to find the number of occurrences in a sorted array. We then looked at linear search and binary search approach to this problem. We discussed time complexity and space complexity of this problem.We hope that this blog has helped you enhance your knowledge regarding program to count number of occurrences in a sorted array and if you would like to learn more, check out our articles on c++. Do upvote our blog to help other ninjas grow. Happy Coding!”

Was this article helpful ?
0 upvotes