- Write a program in C to find the count of a number in a sorted array.
- Algorithm to find the number of occurrences in a sorted array.

Given a sorted integer array of size N and a number K. We have to **find the count of K in given sorted array**.

For Example :

Input Array : 1 2 2 2 2 2 3 4 5

K = 2

Count of 2 is 5

Input Array : 1 2 2 3 4 4 5 7 8 8 8

K = 4

Count of 4 is 2

Let inputArray be a sorted integer array of size N and we want o find count of K in inputArray.

**Method 1 : By using linear search**

- Using a for loop, traverse inputArray from index 0 to N-1.
- Compare each element of inputArray with K and count the occurrences of K.

**Method 2 : By using modified binary search**

- As inputArray is sorted, all duplicate elements are grouped together in adjacent locations.
- Using modified binary search, find the index of first occurrence of K in inputArray. Let it be leftIndex.
- Using modified binary search, find the index of last occurrence of K in inputArray. Let it be rightIndex.
- The count of K in inputArray is equal to (rightIndex - leftIndex + 1).

## C program to find occurrence of a number in sorted array

- getFirstIndex : This function returns the index of first occurrence of K, if K is present in array otherwise -1.
- getLastIndex : This function returns the index of last occurrence of K, if K is present in array otherwise -1.
- getElementCount : This function returns the count of occurrence of K in array.

#include <stdio.h> /* Returns the index of first occurrence of K in sorted array. If is not present then it returns -1. It uses a customized binary search algorithm */ int getFirstIndex(int *array, int left, int right, int K) { int mid; if (right >= left) { /* Get mid index */ mid = (left + right)/2; /* if array[mid] == K, then mid will be the index of first occurrence of K if either mid == 0, or array[mid-1] < K */ if ((array[mid] == K) && (mid == 0 || K > array[mid-1])) /* first occurrence found */ return mid; else if (K > array[mid]) /* Recursively search on right sub array */ return getFirstIndex(array, (mid + 1), right, K); else /* Recursively search on left sub array */ return getFirstIndex(array, left, (mid - 1), K); } return -1; } /* Returns the index of last occurrence of K in sorted array. If is not present then it returns -1. It uses a customized binary search algorithm */ int getLastIndex(int *array, int left, int right, int K, int size) { int mid; if (right >= left) { /* Get mid index */ mid = (left + right)/2; /* if array[mid] == K, then mid will be the index of last occurrence of K if either mid == size-1, or array[mid+1] > K */ if ((array[mid] == K) && (mid == size-1 || K < array[mid+1])) /* Last occurrence found */ return mid; else if (K >= array[mid]) /* Recursively search on right sub array */ return getLastIndex(array, (mid + 1), right, K, size); else /* Recursively search on left sub array */ return getLastIndex(array, left, (mid - 1), K, size); } return -1; } int getElementCount(int *array, int size, int K){ /* get the index of first occurrence of K*/ int firstIndex = getFirstIndex(array, 0, size-1, K); /* get the index of last occurrence of K*/ int lastIndex = getLastIndex(array, 0, size-1, K, size); if(firstIndex == -1 || lastIndex == -1) return -1; /* As array is sorted , all duplicate elements will be in adjacent locations. Hence, total count of K will be lastIndex - firstIndex + 1 */ return lastIndex - firstIndex + 1; } int main(){ int array[9] = {1,1,2,4,4,4,4,4,7}; int count = getElementCount(array, 9, 4); printf("Count of 4 is : %d\n", count); return 0; }Output

Count of 4 is : 5