Searching & Sorting Help

[NicoFlowProductions]

Need someone to overlook my code and double check if i did my assignment correctly.

Write a program that prompts the user to enter the number of elements and the numbers themselves to be placed in an integer array that holds a maximum of 50 elements. The program should then prompt the user for an integer which will be searched for in the array using a binary search.

-A sort routine must be called before the binary search. You may use either the selection sort or the bubble sort. However, the sort must be imple- mented in its own function and not in main.

-Next include a function called by main to implement the binary search.

-Add a value returning function that computes the mean of your data set.

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

/* function prototype */

int get_num_of_ints(
            const int* arr,
            size_t r,
            int N,
            size_t* first,
            size_t* count
    );

int main()
{   
    int N;                                 /* input variable */
    int arr[]={1,1,2,3,3,4,4,4,4,5,5,7,7,7,7,8,8,8,9,11,12,12}; /* sorted */
    size_t r = sizeof(arr)/sizeof(arr[0]); /* right bound */
    size_t first;                          /* first match index */
    size_t count;                          /* total number of matches */

    /* prompts the user to enter input */

    printf( "\nPlease input the integer you would like to find.\n" );
    scanf( "%d", &N );

    int a = get_num_of_ints( arr, r, N, &first, &count );

    /* If the function returns -1 then the value is not found.
        Else it is returned */ 

    if( a == -1)    
        printf( "%d has not been found.\n", N );

    else if(a >= 0){
        printf( "The first matching index is %d.\n", first );
        printf( "The total number of instances is %d.\n", count );
    }

    return 0;
}

/* function definition */

int get_num_of_ints(
        const int* arr,
        size_t r,
        int N,
        size_t* first,
        size_t* count)
{
    int lo=0;    /* lower bound for search */
    int m=0;     /* middle value obtained */
    int hi=r-1;  /* upper bound for search */

    int w=r-1;   /* used as a fixed upper bound to calculate the number of
                    right instances of a particular value. */


    /* binary search to find if a value exists */

    /* first check if the element is out of bounds */

    if( N < arr[0] || arr[hi] < N ){
        m = -1;
    }
    else{ /* binary search to find value if it exists within given params */

        while(lo <= hi){
            m = (hi + lo)/2;

            if(arr[m] < N)
                lo = m+1;
            else if(arr[m] > N)
                hi = m-1;
            else if(arr[m]==N){
                m=m;
                break;
            }
        }
        if (lo > hi)    /* if it doesn't we assign it -1 */
         m = -1;
    }   


    /* If the value is found, then we compute left and right instances of it */ 

    if( m >= 0 ){   

        int j = m-1;    /* starting with the first term to the left */
        int L = 0;  /* total number of left instances */

        /* while loop computes total number of left instances */

        while( j >= 0 && arr[j] == arr[m] ){
            L++;
            j--;
        }


        /* There are six possible outcomes of this. Depending on the outcome,
           we must assign the first index variable accordingly */

        if( j > 0 && L > 0 )
            *first=j+1;
        else if( j==0 && L==0)
            *first=m;
        else if( j > 0 && L==0 )
            *first=m;
        else if(j < 0 && L==0 )
            *first=m; 
        else if( j < 0 && L > 0 )
            *first=0;
        else if( j=0 && L > 0 )
            *first=j+1;

        int h = m + 1;  /* starting with the first term to the right */
        int R = 0;      /* total number of right instances */

        /* while loop computes total number of right instances */
        /* we fixed w earlier so that it's value does not change */ 

        while( arr[h]==arr[m] && h <= w ){
            R++;
            h++;
        }

        *count = (R + L + 1); /* total num of instances stored into count */
        return *first;        /* first instance index stored here */
    }

    /* if value does not exist, then we return a negative value */

    else if( m==-1)
        return -1;
}   

[jlb]

Where did you do the following?

A sort routine must be called before the binary search. You may use either the selection sort or the bubble sort. However, the sort must be imple- mented in its own function and not in main.

And this:

-Next include a function called by main to implement the binary search.

Or this:

Add a value returning function that computes the mean of your data set.

[dhayden]

Lines 94-132 compute the number of matches but I don't see that requirement in the assignment.

Is your assignment in C or C++? This looks like C code to me.

I think your binary search should return the index of the number or -1 if it isn't found. There's no need to pass a pointer to first.