CODEWITHSUNDEEP
arrayscsearchbinary-search
V_ Srj
V_ Srj

Reputation: 15

How to count occurrences of duplicates in array using binary search in C?

I must count the occurrence of an element in the array using binary search in C. I have written the following code but when I use to give an input
Then the output is wrong. I have also tried to predefine the elements in the array & use this code and it works fine. But when I give custom input using scanf statement then the program does not omit the right ans. I have been implementing it in C for hours now. Any help/suggestions would be greatly appreciated.

#include <stdio.h>
int fun(int array[], int s, int x, int key)
{
int ss = 0, e = s - 1;


int n = -1;

while (ss <= e)
{
int middle = (ss + e)/2;


if (x == array[middle]){  

n = middle;
if (key){ 
e = middle - 1;
}
else{ 
ss = middle + 1;
}

}


else if (x < array[middle]){
e = middle - 1;
}

else{
ss = middle + 1;
}
}
return n;
}


int main()
{

int s;
scanf("%d",&s);

int array[s];

for(int i = 0 ; i<s ; i++){

    scanf("%d",&array[i]);
}




for(int i = 0 ; i<s;i++){
    printf("%d ",array[i]);
}
printf("\n");


int x; 
scanf("%d",&x);


int f = fun(array, s, x, 1);


int l = fun(array, s, x, 0);


int t = l - f + 1;

    if (f!= -1){
        printf("%d ", t);
    }

    return 0;
}

Upvotes: 0

Views: 370

Answers (1)

dash-o
dash-o

Reputation: 14452

You can not use binary search to locate data in unsorted array. The elements must be in increasing order for the binary search work. You can use 'qsort' to sort the array in the program, or modify the input to be sorted.

If you modify the input array to: [1 4 5 5 7] , the output will be: 2

Upvotes: 1

Related Questions