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[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
Posted by
Labels: ,