# 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;
}
```

It would be a great help, if you support by sharing :)
Author: zakilive