Here is the problem: you have a sorted array (or a normal array, just sort it using qsort or whatever you wish to use to make it sorted before continuing in this problem) and you want to add a number into that sorted array. You need to know where to put this next number after quickly (suppose we have 10,000,000 elements in this array). We don’t need to know how to insert that new number into the array yet. That’s another problem! Right now we just need to know where.

Here is the example array:

10 20 30 40 50

If I want to insert 25 into this array, where should we insert it at?

10 20 [25] 30 40 50

So, let’s look at other possible cases:

Insert 25:   10 20 [25] 30 40 50 (20 <= 25 < 30)
Insert 5:    [5] 10 20 30 40 50  (5  <  the first element) Insert 55:   10 20 30 40 50 [55] (55 >= the last element)

We will use bsearch for solving this question. Let’s recall the bsearch function. It looks like this:

void* bsearch(void* key, void* first, size_t length, size_t size, int (*compare)(const void* key, const void* wtf));

bsearch can return 2 things. It returns the pointer to the array element we were looking for or a null pointer if a match if not found. Let’s think. Don’t write any code yet…

So, to solve this problem, I will use the bsearch the function to search for the place to put the number K in the sorted array. It will return the pointer to the Nth element of the array if:

  • array[N] <= K and array[N] is the last element in the array (after the last element)
  • array[N] <= K < array[N+1] (somewhere in the array)

And return a null pointer if

  • K < array[0]

Another thing before writing the compare function is the compare function returns an int which specify the direction to go. Return a positive number will make bsearch go right. Returning a negative number will make bsearch go left. Returning 0 means to stop bsearching and return that element. We can now write how function works, if N is the element bsearch is trying to compare with:

  • return 0; if array[N] <= K and (array[N] is the last element or K < array[N+1])
  • return -1; if array[N] < K
  • return 1; otherwise

Now, let’s implement it. First, we need an array to work with.

int array[] = {10, 20, 30, 40, 50};

Second, we need to determine if array[N] is the last element. In the compare function I will use this dirty technique. Use a static pointer to save the last array position. Before we do the bsearch, we will pass a null pointer to the key and the last element as the working element.

int searchcmp(const void* key, const void* wtf) {
    static int* last;
    if (key == 0) {
        last = (int*)wtf;
        return 0;
    } else {
        int* ikey = (int*)key;
        int* iwtf = (int*)wtf;
        // ..... compare code here
    }
}

Now we can write the compare code from what we think above, like this:

int searchcmp(const void* key, const void* wtf) {
    static int* last;
    if (key == 0) {
        last = (int*)wtf;
        return 0;
    } else {
        int* ikey = (int*)key;
        int* iwtf = (int*)wtf;
        if (*iwtf <= *ikey && (iwtf == last || *ikey < *(iwtf + 1)))
            return 0;
        else if (*ikey < *iwtf)
            return -1;
        else
            return 1;
    }
}

Now, how to use it:

First, pass the last element to the function, like this:

searchcmp (0, &array[count - 1]); // tell the function so it knows the last element

Then use bsearch:

result = bsearch(&lookingFor, array, count, sizeof(int), searchcmp); // search

Now the result contains the pointer to insert the next array element after, or null pointer if it needs to be inserted at the beginning of the array:

#include
#include 

int searchcmp(const void* key, const void* wtf) {
    static int* last;
    if (key == 0) {
        last = (int*)wtf;
        return 0;
    } else {
        int* ikey = (int*)key;
        int* iwtf = (int*)wtf;
        if (*iwtf <= *ikey && (iwtf == last || *ikey < *(iwtf + 1)))
            return 0;
        else if (*ikey < *iwtf)
            return -1;
        else
            return 1;
    }
}

int array[] = {10, 20, 30, 40, 50};

int main() {

    int count = sizeof(array) / sizeof(int);
    int* result;
    int lookingFor = 25;
    int i;
    searchcmp (0, &array[count - 1]); // tell the function so it knows the last element
    result = bsearch(&lookingFor, array, count, sizeof(int), searchcmp); // search

    if (result == 0) { // front of the array?
        printf ("[%d] ", lookingFor);
    }
    for (i = 0; i < count; i ++) {
        printf ("%d ", array[i]);
        if (&array[i] == result) { // insert after this element?
            printf ("[%d] ", lookingFor);
        }
    }
    printf ("\n");

    return 0;

}