can't remove duplicates values when creating Set ADT in C

Question

I try to create a simple Set abstract data type in C using dynamic arrays just for learning purposes. I implemented a function called buildSet() that takes as parameters a structure Set, the number n of elements to be imported following by n elements-parameters. My problem is that I should not allow duplicates values, as we know from mathematics. But my code can't pass this requirement. I implemented the Set structure without errors, but when I go to print my set, I see that duplicates exist.

Consider the following example

in main file:

Set S;
buildSet(&S, 6, 5, 20, 2, 3, -8, -8);
for (int i = 0; i < S.size; ++i) {
    printf("%d ", S.elems[i]);
}

The expected output is

5 20 2 3 -8

the actual output is

5 20 2 3 -8 -8

Bellow is the structure I use:

typedef struct {
    int *elems; /* Array contains our set elements. */
    size_t size; /* Number of elements exist in set. */
    long maxSize; /* Maximum allowed number of elements in set. */
    long sum; /* Sum of all elements in set. */
    int *min; /* The minimum element in set. */
    int *max; /* The maximum element in set. */
} Set;

my function prototypes I use:

/**
 * Creates a set structure S 
 * with n elements x1,x2, x3,….
 */
void buildSet(Set *S, size_t n, ...);

/**
 * Checks whether the value x is in the set S.
 */
int isElementOfSet(Set *S, int x);

Bellow is the function body:

void buildSet(Set *S, size_t n, ...) {
    /**
     * Pass each argument, representing a set element,
     * from our variadic function to variadic list.
     */
    va_list setElems; 

    /**
     * Get the number of elements we want to pass
     * to our set.
     */
    va_start(setElems, n);

    /**
     * The number of elements in set structure.
     */
     S->size = 0;

    /**
     * Using this function we don't restrict ourselves
     * of using any number of elements for our set, so
     * we "unset" maxSize member.
     */
     S->maxSize = -1;

     /**
     * We initialize the sum counter. This will
     * allow us to get the sum using sumOfSet()
     * in O(1) time.
     */
     S->sum = 0;

    /**
     * Allocates memory for our set.
     */
    S->elems = malloc(sizeof(int)*(S->size));

    /**
     * Pass each set element, to our set
     * and update the sum counter.
     */
    int elem;
    for (size_t i = 0; i < n; ++i) {
        elem = va_arg(setElems, int);
        if (!isElementOfSet(S, elem)) {
            ++(S->size);
            S->elems = realloc(S->elems, sizeof(int)*(S->size));
            S->elems[(S->size)-1] = elem;

            S->sum += elem;
        }
    }

    /**
     * Frees the variadic list.
     */
    va_end(setElems);
}

int isElementOfSet(Set *S, int x) {
    /**
     * We use binary search in our array-set
     * to find if x belongs to S.
     */
    int middle, left = 0, right = (S->size)-1;
    while (left < right) {
        middle = (left + right)/2;
        if (S->elems[middle] == x) {
            return 1;
        } else {
            if (S->elems[middle] > x) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
    }

    return 0;
}

Answer 1

You have used binary search in your method isElementOfSet. Binary Search can only be applied to an array if the elements of that array are sorted. I dont see anywhere where you have applied some kind of sorting. So I suggest that you change your method isElementOfSet to linear search.

int isElementOfSet(Set *S, int x) {

    int i;
    for(i = 0;i < S->size;++i)
    {
     if(S->elems[i] == x)
       return 1;
    }
    return 0;
}