Being able to implement your own versions of quicksort (as well as other sorts that might be suitable for the occasion) and binary search algorithms is important (you can check my own implementations here).

However, when you are participating in programming contests and challenges the last thing you want to worry about is whether or not your sort/search functions will work correctly and efficiently. The ideal is to master the usage of the built-in functions in whatever language you use, and stick to those.

Since I use C++ on programming competitions I’ll be talking about it here. First of all both the bsearch and the qsort functions are located in the header, so you need to include it.

Before we can use binary search we need to sort the array, so let’s start with the qsort function.

This is the function signature:

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

The four arguments are:

1. base: A pointer to the array (i.e., use the array’s name)
2. num: The size of the array
3. size: The size of each element on the array in bytes(i.e., use sizeof)
4. comparator: A pointer to a function that can compare two elements of the array

The last argument will create some additional work, but it’s worth it cause it gives you the possibility arrays of anything, and not just of the predefined types, as you can create the comparator function to suit your needs.

Just keep in mind that the function needs to return a negative number if the first element is smaller than the second, zero in case they are equal, and a positive number in case the first element is greater than the second. The arguments the function take are pointers to void, so you need to cast them inside the function as well. Below you’ll find a sample piece of code using the qsort function:

#include <iostream>
#include <cstdlib>

#define SIZE 10

int compare (const void *elem1, const void *elem2){
    return *(int*)elem1 - *(int*)elem2;
}

int main(){
    int i;
    int array[SIZE] = {9,1,3,7,0,5,2,6,8,4};

    qsort(array, SIZE, sizeof(int), compare);

    for (i=0;i<SIZE;i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;

    return 0;

}

The bsearch function is very similar to qsort:

void * bsearch ( const void * key, const void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

The only difference is that it has one more argument, which is a pointer to the key you want to search. If the key is found bsearch returns a pointer to it (casted to void pointer), otherwise it returns NULL.

#include <iostream>
#include <cstdlib>

#define SIZE 10

int compare (const void *elem1, const void *elem2){
    return *(int*)elem1 - *(int*)elem2;
}

int main(){
    int i,x;
    int array[SIZE] = {9,1,3,7,0,5,2,6,8,4};

    qsort(array, SIZE, sizeof(int), compare);

    for (i=0;i<SIZE;i++)
        std::cout << array[i] << " ";
    std::cout << std::endl;

    x = 25;
    std::cout << bsearch(&x,array,SIZE,sizeof(int),compare) << std::endl;
    x = 9;
    std::cout << bsearch(&x,array,SIZE,sizeof(int),compare) << std::endl;

    return 0;

}