This is a sorted dynamic array. It allows finding elements in O(log n) time, the same as for a binary search tree. Inserting or deleting elements is in amortized O(n) time because of the need to shift elements to make room or fill gaps.

The main advantages of a sorted array over a binary search tree are:

• Simpler implementation
• Better locality of reference, so improved cache performance
• Iteration does not involve following pointers, just increasing an index variable
• Finding the nth element is O(1), while it is O(n) in a binary search tree
• The array, or a range from it, can be copied to another memory location easily without iteration

Here is the header file:

#ifndef SORTEDARRAY_H
#define SORTEDARRAY_H

#include <dynarray.h>

typedef int (*sortedarray_cmpfn)(const void*, const void*);
typedef void (*sortedarray_forfn)(void*);

struct sortedarray {
	dynarray *array;
	sortedarray_cmpfn compare;
};

typedef struct sortedarray sortedarray;

sortedarray * sortedarray_create(sortedarray_cmpfn compare);
void sortedarray_delete(sortedarray * array);
void * sortedarray_add(sortedarray * array, void * data);
void * sortedarray_remove(sortedarray * array, const void * data);
void * sortedarray_find(const sortedarray * array, const void * data);
void sortedarray_for_each(const sortedarray * array, sortedarray_forfn forfn);
unsigned int sortedarray_get_count(const sortedarray *array);
void * sortedarray_get(const sortedarray *array, unsigned int pos);
void * sortedarray_remove_at(sortedarray *array, unsigned int pos);
int sortedarray_find_index(const sortedarray *array, const void *data);

#endif /* SORTEDARRAY_H */

The implementation:

#include <stdlib.h>

#include <sortedarray.h>

sortedarray * sortedarray_create(sortedarray_cmpfn compare)
{
	sortedarray *array = malloc(sizeof(sortedarray));
	if (array) {
		array->array = dynarray_create(0);
		array->compare = compare;
	}
	return array;
}

void sortedarray_delete(sortedarray * array)
{
	if (array) {
		dynarray_delete(array->array);
		free(array);
	}
}

typedef struct {
	void * data;
	unsigned int pos;
} search_result;

static search_result sortedarray_search(const sortedarray *array, const void *data)
{
	search_result sr;
	unsigned int elements = array->array->count;
	unsigned int offset = 0;
	unsigned int middle = 0;
	
	sr.data = NULL;
	while (elements > 0 && !sr.data) {
		int result;
		middle = elements / 2;
		result = array->compare(data, dynarray_get(array->array, offset + middle));
		if (result > 0) {
			offset = offset + middle + 1;
			elements = elements - (middle + 1);
		}
		else if (result < 0) {
			elements = middle;
		}
		else {
			sr.data = dynarray_get(array->array, offset + middle);
			offset += middle;
		}
	}
	sr.pos = offset;

	return sr;
}

void * sortedarray_add(sortedarray * array, void * data)
{
	search_result result = sortedarray_search(array, data);
	void *existing = result.data;
	if (existing) {
		/* Replace */
		dynarray_set(array->array, result.pos, data);
	}
	else {
		/* Add new */
		dynarray_insert(array->array, result.pos, data);
	}
	return existing;
}

void * sortedarray_remove(sortedarray * array, const void * data)
{
	search_result result = sortedarray_search(array, data);
	if (result.data) {
		dynarray_remove(array->array, result.pos);
	}
	return result.data;
}

void * sortedarray_find(const sortedarray * array, const void * data)
{
	search_result result = sortedarray_search(array, data);
	return result.data;
}

void sortedarray_for_each(const sortedarray * array, sortedarray_forfn forfn)
{
	dynarray_for_each(array->array, forfn);
}

unsigned int sortedarray_get_count(const sortedarray *array)
{
	return array->array->count;
}

void * sortedarray_get(const sortedarray *array, unsigned int pos)
{
	return dynarray_get(array->array, pos);
}

void * sortedarray_remove_at(sortedarray * array, unsigned int pos)
{
	return dynarray_remove(array->array, pos);
}

int sortedarray_find_index(const sortedarray *array, const void *data)
{
	int index = -1;
	search_result result = sortedarray_search(array, data);
	if (result.data) {
		index = result.pos;
	}
	return index;
}

An example program:

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

#include <sortedarray.h>

int main(void)
{
    sortedarray * array;
    const char * result;
    unsigned int e;
    char * elements[] = {"orange", "apple", "pear", "grapefruit", "cherry", "plum"};
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    array = sortedarray_create((sortedarray_cmpfn)strcmp);
    for (e = 0; e < n; e++) {
        sortedarray_add(array, elements[e]);
    }
    sortedarray_for_each(array, (sortedarray_forfn)puts);
    for (e = 0; e < n; e++) {
        result = sortedarray_find(array, elements[e]);
        if (result) {
            printf("Found: %s at %d\n", result, 
                    sortedarray_find_index(array, elements[e]));
        }
        else {
            printf("Couldn't find %s\n", elements[e]);
        }
    }
    for (e = 0; e < n; e++) {
        result = sortedarray_remove(array, elements[e]);
        if (result) {
            printf("Removed: %s\n", result);
        }
        else {
            printf("Couldn't remove %s\n", elements[e]);
        }
    }
    sortedarray_delete(array);

    return 0;
}