{"post":"

Problem: 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:-

Linear Search
Binary Search

# Approach 1

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

Code (Linear Search):

#include <iostream>\nusing namespace std;\n\n// Function returns number of times p occurs in array\nint countrepeat(int array[], int size, int p)\n{\n    int ans = 0;\n    for (int i = 0; i < size; i++)\n        if (array[i] == p)\n            ans++;\n    return ans;\n}\n\n// Driver code\nint main()\n{\n    int array[] = { 32, 32, 54, 65, 78, 78, 78, 78, 85 };\n    int size = sizeof(array) / sizeof(array[0]);\n    int p = 78;\n    cout << p << \" is repeated \" << countrepeat(array, size, p) << \" times\";\n    return 0;\n}\n\n

Output

78 is repeated 4 times\n\n

Time Complexity: O(n)

# Approach 2

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 initialize the start value as mid+1 else last is initialized as mid-1.

Code (Binary Search):

#include <iostream>\nusing namespace std;\n\n// C++ program to count occurrences of an element\n\n//function returns the position of p in given array\nint binarysrch(int array[], int l, int r, int p)\n{\n    if (r < l)\n        return -1;\n\n    int mid = l + (r - l) / 2;\n\n    // If element is found at the middle\n    if (array[mid] == p)\n        return mid;\n\n    // If element is smaller than mid, then\n    // it can only be there in left subarray\n    if (array[mid] > p)\n        return binarysrch(array, l, mid - 1, p);\n\n    // Else the element can only be there\n    // in right subarray\n    return binarysrch(array, mid + 1, r, p);\n}\n\n// function returns number of times p occurs in array\nint countrepeat(int array[], int size, int p)\n{\n    int token = binarysrch(array, 0, size - 1, p);\n\n    // If element is not found\n    if (token == -1)\n        return 0;\n\n    // Counting elements on left\n    int count = 1;\n    int left = token - 1;\n\n    while (left >= 0 && array[left] == p)\n        count++, left--;\n\n    // Counting elements on right\n    int right = token + 1;\n    while (right < size && array[right] == p)\n        count++, right++;\n\n    return count;\n}\n\n// Driver code\nint main()\n{\n    int array[] = { 1, 12, 15, 15, 15, 30, 45, 76, 80 };\n    int size = sizeof(array) / sizeof(array[0]);\n    int p = 15;\n    cout << countrepeat(array, size, p);\n    return 0;\n}\n\n

Output

3\n\n

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

\n","title":"Count frequency of number in sorted array Problem","authorDetails":{"name":"Prabhnoor Maingi","slug":"prabhnoor-maingi"},"description":"We have to count the frequency of number i.e. the count number of occurrences of a number in the given sorted array using C++ with linear search and binary search approach.","slug":"count-frequency-of-number-in-sorted-array-problem/","articleId":"636a83447bb1ce5072622b77","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}