{"post":"

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

Linear Search
Binary Search

# Approach 1(Linear Search)

In linear search, we iterate through the elements of an array one by one and compare each element with the element we are searching for (p). If we find a match, we return the index of the element in the array. Otherwise, we continue searching until we reach the end of the array or we determine that the element is not present in the array.

Code (Linear Search):

#include <iostream>\n\n// Function returns number of times p occurs in array\nint countrepeat(int array[], int size, int p) {\n    int ans = 0;\n    for (int i = 0; i < size; i++) {\n        if (array[i] == p) {\n            ans++;\n        }\n    }\n    return ans;\n}\n\n// Driver code\nint main() {\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    std::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(Binary Search)

Find the middle element of the array using integer division: mid = (start + last) / 2
Define the search range using the start and last indices
Compare the value of the element we are searching for (p) with the value at the middle of the array (array[mid])
If p is greater than array[mid], set the starting index of the search range to mid + 1
If p is less than or equal to array[mid], set the ending index of the search range to mid - 1
Repeat the process until the element is found or the search range becomes empty.

Code (Binary Search):

#include <iostream>\n#include <stdio.h>\n#include <conio.h>\n\n// C++ program to count occurrences of an element\n\n//function returns position of p in given array\nint binarysrch(int array[], int l, int r, int p) {\n    if (r < l) {\n        return -1;\n    }\n    int mid = l + (r - l) / 2;\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    int token = binarysrch(array, 0, size - 1, p);\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    while (left >= 0 && array[left] == p) {\n        count++;\n        left--;\n    }\n    // Counting elements on right   \n    int right = token + 1;\n    while (right < size && array[right] == p) {\n        count++;\n        right++;\n    }\n    return count;\n}\n\n// Driver code\nint main() {\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    std::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","authorDetails":{"name":"Prabhnoor Maingi","slug":"prabhnoor-maingi"},"description":"Learn how to use C++ to count the frequency of a specific number in a sorted array. Get step-by-step instructions and examples of how to implement this algorithm using a binary search approach. ","slug":"count-frequency-of-number-in-sorted-array/","articleId":"636a83447bb1ce5072622b62","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}

# Approach 1(Linear Search)

# Approach 2**(Binary Search)**

# Approach 2(Binary Search)