How to modify my binary search

general
,
1

Hello,I want to modify my iterative binary search so that i can count number of occurrence of an number(say x) in a sorted array {a1,a2,a3,a4…an}.Here’s the link of my implementation done so far.Any help will be appreciated.

1 Like
2

It would make more sense to simply move linearly left and right once you find your index of the integer you are searching for.

EDIT:
I agree with @adi28galaxyak, if you have to calculate occurrence regularly, then creating an array that stores the frequency of all elements would be better. This would be a one time investment of O(n).

On the other hand, if you want to save space or only want to check occurrence once and do it really quickly, first doing a binary search (investment = O(log n) and THEN moving linearly to calculate frequency of that number would make sense.

3

#include <stdio.h>

int b(int a[],int i,int n)
{

int l,u,m;
l=0;			 u=n;
while(l<=u)

{

	m=(l+u)/2;
    if(a[m]==i)

{

        if(a[m-1]!=i)
        return m;
        u=m-1;
    }
    else if(a[m]>i) {
        u=m-1;
    }
    else
        l=m+1;
}
return -1;

}

int main()
{

int n,q,a[100001],x,p,i;
scanf("%d %d",&n,&q);
for(i=0;i<n;i++)

{

    scanf("%d",&a[i]);
}
i=1;
while(i++<=q)

{

        scanf("%d",&p);
        printf("%d\n",b(a,p,n-1));
}
return 0;

}

IT WILL GIVE YOU THE FIRST OCCURENCE OF ANY NO SIMILARILY YOU CAN MAKE PROGRAM LAST OCCURENCE OF NO AND THE SUBTRACT THEN INDEXES OF THOSE TWO OCCURENCE YOU WILL BE ABLE TO COUNT THE NO OF OCCURENCE

4

Binary Search is a search algorithm which is used to search an element. If you use it to complete your task it becomes a clumsy task.

For this kind of problem make an array of the size of maximum number and store zero at each index of the array. Now run a loop and increment the value at the scaned integer index in the array. This helps you to complete the task in O(n) time. This gives you the frequency of all the elements.

For more refer to link.