Binary search in C using bsearch

apple-cross

This is an example C program which illustrates using bsearch to do a binary search in a sorted list.

#include <stdio.h>

/* bsearch is declared in "stdlib.h". */
#include <stdlib.h>

/* strcmp is declared in "string.h". */
#include <string.h>

/* The array to search in needs to be sorted in alphabetical order. */

static const char * fruit[] = {
    "apple",
    "banana",
    "coconut",
    "grapefruit",
    "guava",
    "mango",
    "mangosteen",
    "orange",
    "pineapple",
};

#define n_fruit (sizeof (fruit) / sizeof (const char *))

static int
compare_fruit (const void * a, const void * b)
{
    /* "a" is always just the key but "b" is a member of the array
       "fruit", so it needs to be dereferenced. */

    return strcmp (a, *(const char**) b);
}

/* Perform the binary search. */

static void
binary_search (const char * key)
{
    const char * found;
    found = bsearch (key, fruit, n_fruit, sizeof (const char *),
                     compare_fruit);
    if (found) {
        printf ("%s is a fruit.\n", key);
    }
    else {
        printf ("%s is not a fruit.\n", key);
    }
}

int main ()
{
    binary_search ("apple");
    binary_search ("potato");

    return 0;
}

(download)

The output of the example looks like this:

apple is a fruit.
potato is not a fruit.


Copyright © Ben Bullock 2009-2017. All rights reserved. For comments, questions, and corrections, please email Ben Bullock (benkasminbullock@gmail.com). / Privacy / Disclaimer