Browse Source Download (without any required ccan dependencies)

Module:

asearch

Summary:

typesafe binary search (bsearch)

Author:

Rusty Russell <rusty@rustcorp.com.au>

Dependencies:

Description:

An ordered array of objects can be efficiently searched using a binary search algorithm; the time taken is around log(number of elements).

This version uses macros to be typesafe on platforms which support it.

Example:

#include <ccan/asearch/asearch.h>
#include <stdio.h>
#include <string.h>

static int cmp(const char *key, char *const *elem, void *ctx)
{
        return strcmp(key, *elem);
}

int main(int argc, char *argv[])
{
        char **p;

        if (argc < 2) {
                fprintf(stderr, "Usage: %s <key> <list>...\n"
                        "Print position of key in (sorted) list\n",
                        argv[0]);
                exit(1);
        }

        p = asearch(argv[1], &argv[2], argc-2, cmp, NULL);
        if (!p) {
                printf("Not found!\n");
                return 1;
        }
        printf("%u\n", (int)(p - &argv[2]));
        return 0;
}

License:

LGPL (v2.1 or any later version)