Interview: Find Occurances in an Array – Binary Search Application

Some theory:

code:

/*
Count Frequency in an Array
Syed Ahmed Zaki -- 2017
*/


#include<stdio.h>
int findcount(int A[],int n,int x)
{
    int i,count=0;

    for(i=0; i<=n-1; i++)
    {
        if(A[i]==x)
        {
            count=count+1;
        }
    }
    return count;
}

int main()
{
    int A[]= {1,1,3,3,5,5,5,5,9,9,11};
    int x;
    scanf("%d",&x);
    int i=findcount(A,11,x);
    printf("%d is %d times",x,i);
    return 0;
}

Optimized Code: Using Binary Search

/*
Count Frequency in an Array(Optimized Version)
Syed Ahmed Zaki -- 2017
*/


#include<cstdio>
int findcount(int A[],int n,int x, bool searchFirst)
{
    int low=0, high=n-1, result=-1;
    while(low<=high)
    {
int        mid=(low+high)/2;
        if(A[mid]==x)
        {
            result=mid;
            if(searchFirst){
            high=mid-1; //gp on searching towards left(indice onujayi)
            }
            else{
            low=mid+1;//go on searching towards right(higher indices)
            }
        }
        else if(x<A[mid])
        {
            high=mid-1;
        }
        else
        {
            low=mid+1;
        }
    }
    return result;

}

int main()
{
    int A[]= {1,1,3,3,5,5,5,5,9,9,11};
    int x;
    scanf("%d",&x);
    int firstIndex=findcount(A,sizeof(A)/sizeof(A[0]),x,true);
    if(firstIndex == -1){
        printf("Count of %d is %d",x,0);
    }
    else{
    int lastIndex=findcount(A,sizeof(A)/sizeof(A[0]),x,false);
        printf("%d is %d times",x,lastIndex-firstIndex+1);
    }

    return 0;
}