RUN


Count frequency of number in sorted array

Given: A sorted array. We have to count the frequency of number i.e. the count number of occurrences of a number in the given sorted array.

Example: 

Arr[]={ 5,10,15,15,15,25,30,60,80} , p= 15

Output : 3

Explanation: Number 15 occurs 3 times in the sorted array.

This problem can be done in two ways:-

  1. Linear Search
  2. Binary Search

# Approach 1(Linear Search)

In linear search, we compare each element with the element to be found as we traverse through the array.

Code (Linear Search):

#include <iostream>

// Function returns number of times p occurs in array

int countrepeat(int array[], int size, int p)

{

	int ans = 0;

	for (int i = 0; i < size; i++)

		if (array[i] == p)

			ans++;

	return ans;

}

// Driver code

int main()

{

	//clrscr();

	int array[] = { 32, 32, 54, 65, 78, 78, 78, 78, 85 };

	int size = sizeof(array) / sizeof(array[0]);

	int p = 78;

	std::cout << p << " is repeated " << countrepeat(array, size, p) << " times";

	return 0;

}

 

Time Complexity:  O(n)

# Approach 2(Binary Search)

In binary search, we find the middle element ((start+last)/2) (Here, start corresponds to first element and last corresponds to the last element) and check if the element to be found is smaller or greater than value present at the middle. If the element to be found is greater then we initialise the start value as mid+1 else last is initialised as mid-1.

Code (Binary Search):

#include <iostream>
#include <stdio.h>
#include <conio.h>

// C++ program to count occurrences of an element 

//function returns position of p in given array

int binarysrch(int array[], int l, int r, int p)

{

	if (r < l)

		return -1;

	int mid = l + (r - l) / 2;

	// If element is founf at the middle 

	if (array[mid] == p)

		return mid;

	// If element is smaller than mid, then 

	// it can only be there in left subarray 

	if (array[mid] > p)

		return binarysrch(array, l, mid - 1, p);

	// Else the element can only be there 

	// in right subarray 

	return binarysrch(array, mid + 1, r, p);

}

// function returns number of times p occurs in array 

int countrepeat(int array[], int size, int p)

{

	int token = binarysrch(array, 0, size - 1, p);

	// If element is not found 

	if (token == -1)

		return 0;

	// Counting elements on left 

	int count = 1;

	int left = token - 1;

	while (left >= 0 && array[left] == p)

		count++, left--;

	// Counting elements on right  

	int right = token + 1;

	while (right < size && array[right] == p)

		count++, right++;

	return count;

}

// Driver code

int main()

{

	int array[] = { 1, 12, 15, 15, 15, 30, 45, 76, 80 };

	int size = sizeof(array) / sizeof(array[0]);

	int p = 15;

	std::cout << countrepeat(array, size, p);

	return 0;

}

Time Complexity : O(Log n + count)  //where count is number of occurrences.

 

Report Error/ Suggestion

Related Posts:





CopyRight © 2020

CopyRight © 2020