C homework help: Searching through arrays

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

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).

Answer 2

Since you need the number of occurrences, you need to search through each element, right?

Why not simplify things and just do a linear scan? Here's some pseudocode:

function get_num_of_ints(arr, n){
    first_index = -1
    count = 0

    for(i = 0; i < length(arr); i++)
        if(x == n){
            count++
            if(first_index == -1)
                first_index = i
        }

    return count, first_index
}

Answer 3

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 4

I don't have a C compiler in the computer I'm sitting now, so I can't test it, but I see that in the first while-loop of your function you're saying:

else if(arr[m]==N)
            m=m;
            break;

The break statement is outside the if in this case, so the while loop will execute only once each time.

I don't know if this causes the error though.

Answer 5

In get_num_of_ints() function you are using pointer fptr without allocating memory to it.

Answer 6

The segmentation fault comes from get_num_of_ints() in lines 74, 77, and 87.

if( j>= 0 && L > 0 )
    *fPtr=j;
else
    *fPtr=m;
...
*countPtr = (R + L + 1);

You have not assigned a memory address to the pointers, and thus you are using an arbitrary memory location in these lines.

It doesn't seem like there's any real reason to be using a pointer for these variables anyway. Try changing them from pointers to size_t to just variables of type size_t.

size_t fPtr;
size_t countPtr;

Answer 7

There are multiple problems with your code.

   size_t r = sizeof(arr[i])/sizeof(int);                      /* right bound */ 

This will always evaluate to 1. You are lucky that sizeof is a compile time thingy, otherwise this line of code could blow up because you are using an uninitialized value of i.

this should be

   size_t r = sizeof(arr)/sizeof(arr[0]);                      /* right bound */ 

Once you fix this bug, you will hit segfault because array indexing will be 0 to r-1 not 0 to r in this function:

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

I didn't check the rest more closely, but hope it helps. I would recommend that you run this through a debugger a see what is exactly happening.

Answer 8

Hi everybody,

Thanks to everybody's comments, I was able to find all the bugs in my program, and use the gdb debugger too. Anyways, I no longer have my seg. fault errors when I run the program; however, I have some sort of logic problem becauase when I prompt the user for an input,and say the user types 4, then the outputs for # of occurence and location of first occurrence are garbage values.

I get:

Please input the integer you would like to find.
4
The first index is -1075300456.
The total number of values is 12169204.

This revolves around the issue I had earlier with the last two parameters in my function. At the bottom, in the function definition, I want count to be the total number of occurrences found in the list.

#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)/sizeof(arr[0]) - 1;                  /* right bound */
    size_t f;                                       /* first match index */


    size_t count;                                       /* total number of matches */


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

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

    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;


    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( j >= 0 && arr[j] == arr[m] ){
            L++;
            j--;
        }


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

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

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

        count = (R + L + 1);
        return f;
    }

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

Answer 9

1. As everyone pointed out countPtr and fPtr needs to be allocated with memory

   size_t *fPtr = malloc(sizeof(size_t));

2. Make sure you intialize "i" with some value before using it

3. Compile the program (if you are in Linux) with # gcc -g -Wall <your c file name> -o arraysort

   Start the debugger, step through the code to find out valeues, I found several funny values for r, arr[m],

   #gdb ./arraysort

   b run [inspect variables here]

HTH