# Program to Find Occurrences of a Number in Sorted Array

• 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.
Time Complexity : O(n)

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).
Time Complexity : O(Logn)

## 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 = {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
```