Find the occurrences of X in the given sorted array

In the given sorted array, find the number of times X is coming. (X is integer)

Example

input array: [1,2,2,2,2,3,3,3,4,4,4,5,5]
occurrences of 1 here output : 1
occurrences of 2 here output : 4
occurrences of 3 here output : 3
occurrences of 4 here output : 3
occurrences of 5 here output : 2

ALGORITHM 1

TIME COMPLEXITY – O(logN)
SPACE COMPLEXITY – O(1)

1. Simply do a modified binary search such that
2. Find the first occurrence of X like this:

  1.  Check if the middle element of the array is equal to X.
  2. If equal or greater element is at mid then reduce the partition from start to mid-1. As we will have the  first occurrence in the left side of mid of array then.
  3. If the middle element is smaller then we will check in the right side of middle element as the array is sorted.
  4. Return the first occurrence.

3. Now similarly find the last occurrence of X in the array by doing

  1. Check if the middle element of the array is equal to X
  2. If equal or smaller element is at mid then increase the partition from mid+1 to high. As we will have the  last occurrence in the right side of mid of array then.
  3. Else search in left side of array
  4. return the last occurrence

4. Now the number of occurrences is simply last occurrence – first occurrence.

Algorithm 1 Working Example 

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {1,2,2,3,3,3,4,5,8,8,8,8,9};//array
	int N = sizeof(arr)/sizeof(arr[0]); // size of array
	
	int X; // number whose count is to be found out
	cin >> X;
	int count = 0; //initially its count is zero
	for(int i = 0 ; i < N; i++)
		if(arr[i] == X)
			count++;
		
		cout<<count;
	
	return 0;
}
Try It

ALGORITHM 2

TIME COMPLEXITY – O(logN)
SPACE COMPLEXITY – O(1)

  1. Simply do the same approach as algorithm 1 but using upper_bound() and lower_bound functions.
  2. Calculate the last occurrence using upper_bound() and first occurrence via lower_bound() functions.
  3. Number of occurrences is simply the index obtained by upper_bound() –
  4. lower_bound().

Low_bound(), Upper_bound are STL functions. Standard Template Library (STL)

Algorithm 2 Working Example

Input array

 

Lower_bound(5, input array) = 3
Upper_bound(5, input array) = 6

Therefore,
Total number of occurrences of 5 = Upper_bound – Lower_bound
                        = 6 – 3
                        = 3.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] = {1,2,2,3,3,3,4,5,8,8,8,8,9};//array
	int N = sizeof(arr)/sizeof(arr[0]); // size of array
	
	int X; // number whose count is to be found out
	cin >> X;
	int count = 0; //initially its count is zero
	count  = upper_bound(arr,arr+N,X) - lower_bound(arr,arr+N,X); //last occurence - first occurence is the count	
	cout<<count;
	
	return 0;
}
Try It

 

ALGORITHM  3

TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – O(1)

  1. Simply run a loop.
  2. If we get an element equal to X start increasing the count
  3. Till we see X increase the count and as soon as we get a number different from X then we display the obtained count as it is a sorted array.

Algorithm 3 Working Example

Loop Ends here because, element other than 5 came and there cannot be any other occurrences of 5 in the array.

Therefore,

Total number of occurrences of 5 in the given array is count = 3.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int first_occurence(int arr[],int N,int X)
{
	int low = 0 , high = N-1;
	int first = INT_MAX;
	while(low <= high)
	{
		int mid = low + ((high-low)>>1);
		if(arr[mid] == X) //if found then check the left part for further occurence
		{
			if(mid < first)
			first = mid;
			high = mid-1;
		}
		else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
			low = mid + 1;
		else if (arr[mid] > X)//if middle element is larger than X check in left subpart
			high = mid - 1;
	}
	
	return first;
}
int last_occurence(int arr[],int N,int X)
{
	int low = 0 , high = N-1;
	int last = INT_MIN;
	
	while(low <= high)
	{
		int mid = low + ((high-low)>>1);
		if(arr[mid] == X) //if found check in right subpart for last occurence
		{
			if(mid > last)
			last = mid;
			low = mid+1;
		}
		else if(arr[mid] < X) //if the middle element is smaller than X check in right subpart
			low = mid + 1;
		else if (arr[mid] > X)//if middle element is larger than X check in left subpart
			high = mid - 1;
	}
	
	return last;
}
int main()
{
	int arr[] = {1,2,2,3,3,3,4,5,8,8,8,8,9};//array
	int N = sizeof(arr)/sizeof(arr[0]); // size of array
	
	int X; // number whose count is to be found out
	cin >> X;
	int count = 0; //initially its count is zero
	
	int last = last_occurence(arr,N,X);

	if(last != INT_MIN)
		count += last;
	
	int first = first_occurence(arr,N,X);
	if(first != INT_MAX)
		count -= first;
	cout<<first<<endl;
	cout<<last<<endl;	
	cout<<count;
	
	return 0;
}
Try It
 


Next > < Prev
Scroll to Top