C homework help: Searching through arrays [closed]

Question

I'm working on a problem where I'm given a sorted array of integers, and I am supposed to take an input from the user, search for the input, and return the first instance of that input (if it exists) and the number of times it appears.

I wrote a program with the following approach: I take an input from the user. I then use binary search to find the value. If it exists, then I store the index as m. After that, I write two while loops. The first loop checks for the number of occurrences of the value to the left and the second does the same, but to the right. For example, the binary search might be looking for 5, and it finds it. However, it lands on the 3rd one, ie. {.....5,5,**5**,5....}. The first while loop will count the two the the left and the second while loop will count the one to the right. Then I'll sum them all up and return the total number of instances. If the the input value does not exist, then I skip the afore-mentioned code and simply return -1.

In the body of the main function, I then check the return value. If it is -1, I tell the user that the value has not been found. If the return value is >=0, then I print the required info.

Anyways, I have written up the C code for the program, but I cannot get it to work properly. I get a seg. fault error, I don't know what I'm doing wrong though. Anyways, any help would be appreciated. I've been pounding my head on this problem for awhile. It's been interesting and hard, and I think I have the right logic; but I cannot get it to work properly. Anyways, here is the code:

#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* f, size_t* count );

int main()
{   
    int i;
    int N;                                      /* input variable */
    int arr[]={1,1,2,3,4,4,4,4,5,5,6,7,7,7,7,8,9,9};                    /* array of sorted integers */
    size_t r = sizeof(arr[i])/sizeof(int);                      /* right bound */
    size_t f;                                       /* first match index */
    size_t *fPtr;
    fPtr = &f;
    size_t count;                                       /* total number of matches */
    size_t *countPtr;                                   
    countPtr = &count;  

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

    int a = get_num_of_ints( arr, r, N, fPtr, countPtr );

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

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

    return 0;
}

/* function definition */

int get_num_of_ints( const int* arr, size_t r, int N, size_t* f, size_t* count )
{
    int l = 0;
    int m;
    int w=r;
    size_t *fPtr;
    size_t *countPtr;


    while(l <= r){
        m = l +(r - l)/2;
        if(arr[m] < N)
            l = m+1;
        else if(arr[m] > N)
            r = m-1;
        else if(arr[m]==N)
            m=m;
            break;
    }
    if( l > r)
        m = -1;

    if( m >= 0 ){   

        int j = m-1;
        int L = 0;

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


        if( j>= 0 && L > 0 )
            *fPtr=j;
        else
            *fPtr=m;

        int h = m + 1;
        int R = 0;

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

        *countPtr = (R + L + 1);
        return *fPtr;
    }

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

Answer 1

while(arr[j] == arr[m] && j >= 0)

You should switch the order of the two conditions here, or you'll try to read arr[-1]. Same thing for the second while loop.

Another problem is that r should start at 1 less than the array size, since arr[array_size] is past the end.

Edit:

A serious problem is that you are writing to the uninitialized pointers countPtr and fPtr when you should be writing to *count and *f. This is probably what's causing the segfault. This would have been easy to spot in a debugger.

Answer 2

1. Use variable names that mean something. You might find the problem immediately.

2. Run the program in a debugger and step through the code; you should see where things are going wrong pretty quickly. (Hint, what's fPtr used for in get_num_of_ints? There are other bugs too as others have pointed out).