Count number of occurrences (or frequency) in a sorted array
Given a sorted array arr[] and a number x, write a function that counts the occurrences of x in arr[]. Expected time complexity is O(Logn)
Examples:
Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 2 Output: 4 // x (or 2) occurs 4 times in arr[] Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 3 Output: 1 Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 1 Output: 2 Input: arr[] = {1, 1, 2, 2, 2, 2, 3,}, x = 4 Output: 1 // 4 doesn't occur in arr[]
Method 1 (Linear Search)
Linearly search for x, count the occurrences of x and return the count.
 C

// C++ program to count occurrences of an element
#include<bits/stdc++.h>
using
namespace
std;
// Returns number of times x occurs in arr[0..n1]
int
countOccurrences(
int
arr[],
int
n,
int
x)
{
int
res = 0;
for
(
int
i=0; i<n; i++)
if
(x == arr[i])
res++;
return
res;
}
// Driver code
int
main()
{
int
arr[] = {1, 2, 2, 2, 2, 3, 4, 7 ,8 ,8 };
int
n =
sizeof
(arr)/
sizeof
(arr[0]);
int
x = 2;
cout << countOccurrences(arr, n, x);
return
0;
}
Output :
4
Time Complexity: O(n)
Method 2 (Use Binary Search)
1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);
 C

/* if x is present in arr[] then returns the count of occurrences of x,
otherwise returns 1. */
int
count(
int
arr[],
int
x,
int
n)
{
int
i;
// index of first occurrence of x in arr[0..n1]
int
j;
// index of last occurrence of x in arr[0..n1]
/* get the index of first occurrence of x */
i = first(arr, 0, n1, x, n);
/* If x doesn't exist in arr[] then return 1 */
if
(i == 1)
return
i;
/* Else get the index of last occurrence of x. Note that we
are only looking in the subarray after first occurrence */
j = last(arr, i, n1, x, n);
/* return count */
return
ji+1;
}
/* if x is present in arr[] then returns the index of FIRST occurrence
of x in arr[0..n1], otherwise returns 1 */
int
first(
int
arr[],
int
low,
int
high,
int
x,
int
n)
{
if
(high >= low)
{
int
mid = (low + high)/2;
/*low + (high  low)/2;*/
if
( ( mid == 0  x > arr[mid1]) && arr[mid] == x)
return
mid;
else
if
(x > arr[mid])
return
first(arr, (mid + 1), high, x, n);
else
return
first(arr, low, (mid 1), x, n);
}
return
1;
}
/* if x is present in arr[] then returns the index of LAST occurrence
of x in arr[0..n1], otherwise returns 1 */
int
last(
int
arr[],
int
low,
int
high,
int
x,
int
n)
{
if
(high >= low)
{
int
mid = (low + high)/2;
/*low + (high  low)/2;*/
if
( ( mid == n1  x < arr[mid+1]) && arr[mid] == x )
return
mid;
else
if
(x < arr[mid])
return
last(arr, low, (mid 1), x, n);
else
return
last(arr, (mid + 1), high, x, n);
}
return
1;
}
/* driver program to test above functions */
int
main()
{
int
arr[] = {1, 2, 2, 3, 3, 3, 3};
int
x = 3;
// Element to be counted in arr[]
int
n =
sizeof
(arr)/
sizeof
(arr[0]);
int
c = count(arr, x, n);
printf
(
" %d occurs %d times "
, x, c);
getchar
();
return
0;
}
Output:
3 occurs 4 times
Time Complexity: O(Logn)
Programming Paradigm: Divide & Conquer
Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits: http://www.geeksforgeeks.org
We have built the accelerating growthoriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at
http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide