Number of occurrence of an element in a sorted array

Question

I want to find the number of occurrence of an element in a sorted array. I used BinarySearch logic to implement this. But I am not getting the correct output. I am using this logic

numberOfOccurrence = findLastOccurrence - firstOccurrence + 1

This is my code

#include<stdio.h>
int find_last(int a[],int n,int key)
{
    int low = 0;
    int high = n-1;
    int result = -1;
    while(low<=high)
    {
        int mid = (low+high)/2;
        if(a[mid]==key)
            {
                result = mid;
                low = mid+1;
            }
        else if(key<a[mid])
            high = mid-1;
        else 
            low = mid+1;
    }
    return result;
}
int find_first(int a[],int n,int key)
{
    int low = 0;
    int high = n-1;
    int result = -1;
    while(low<=high)
    {
        int mid = (low+high)/2;
        if(a[mid]==key)
            {
                result = mid;
                high = mid-1;
            }
        else if(key<a[mid])
            high = mid-1;
        else 
            low = mid+1;
    }
    return result;
}
int find_count(int a[],int n,int x)
{
    int first,last;
    first =  find_first(a,n,x);
    last = find_last(a,n,x);
    printf("\nLast index is %d",last+1);
    printf("\nFirst index is %d",first+1);
    printf("\nlast-first+1 is %d",last - first + 1);
    return (last-first+1);
}
main()
{
    int a[10],flag=0,n,x,count=0,i;
    printf("\nEnter the number of elements ");
    scanf("%d",&n);
    printf("\nEnter %d elements ",n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }   
    printf("\n Elements are \n");
    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
    printf("\n Enter the key ");
    scanf("%d",&x);
    count = find_count(a,n,x);
    printf("%d","\n The count is %d \n",count);
}

but some problem in the statement return (last-first+1);. It is returning some large values.

I tested in CFree with mingw and Visual Studio 2010.

Answer 1

You don't even need a binary search for this (and in any case the array would need to be sorted). A simple traverse of the array is all that is needed, whether or not it is sorted. Plus a little error checking for good form (GIGO), which makes this program look much bulkier than it would without. The key part of the code is only 3 lines.

#include<stdio.h>

#define NUMBERS 10

int main ( ) {
    int a[NUMBERS], n, x, count=0, i;

    printf("\nEnter the number of elements ");
    if (1 != scanf("%d",&n))
        return 1;                           // bad entry
    if (1 > n || NUMBERS < n)
        return 1;                           // number out of range

    printf("\nEnter %d elements ", n);
    for(i=0; i<n; i++){
        if (1 != scanf("%d", &a[i]))
        return 1;                           // illegal number
    }

    printf("\nElements are \n");
    for(i=0; i<n; i++){
        printf("%d ", a[i]);
    }

    printf("\nEnter the key ");
    if (1 != scanf("%d", &x))
        return 1;                           // bad entry

    for(i=0; i<n; i++){                     // <--- every element
        if (x == a[i])                      // <--- find matching key
            count++;                        // <--- keep a tally
    }

    printf("\nThe count is %d\n", count);   // (corrected) result
    return 0;
}

Answer 2

printf("%d","\n The count is %d \n",count);

change it to :

printf(" The count is %d \n",count);

You connot put more than one " " in printf