Δυαδική αναζήτηση

Στη δυαδική αναζήτηση (binary search) η εύρεση της εγγραφής στον ταξινομημένο πίνακα γίνεται αναζητώντας το στοιχείο στη μέση του πίνακα, στη συνέχεια στη μέση της μέσης κ.ο.κ.
Αν ο πίνακας έχει Ν στοιχεία θα απαιτηθούν κατά μέσο όρο log2 N συγκρίσεις.

Η βιβλιοθήκη της C υλοποιεί τον αλγόριθμο αυτό στη συνάρτηση bsearch:

#include <stdlib.h>

void *bsearch(const void *key, const void *base, size_t num, size_t width, int (*compare)(const void *elem1, const void *elem2));

Η συνάρτηση αναζητά την τιμή που δείχνεται από το δείκτη key σε έναν ταξινομημένο πίνακα δεδομένων με βάση μια συνάρτηση σύγκρισης.
Η συνάρτηση έχει τις παρακάτω παραμέτρους:

key
Δείκτης στην τιμή για την οποία εκτελείται η αναζήτηση.
base
Δείκτης στην αρχή του πίνακα των δεδομένων που θα εκτελεστεί η αναζήτηση.
num
Αριθμός των δεδομένων στον πίνακα.
width
Το μέγεθος κάθε στοιχείου του πίνακα (π.χ. sizeof(int), sizeof(struct s_elem *)).
compare
Δείκτης σε συνάρτηση που συγκρίνει δύο στοιχεία με βάση δείκτες σε αυτά. Η συνάρτηση compare (όπως και αυτή της qsort) πρέπει να επιστρέφει τις παρακάτω τιμές:

< 0
αν το elem1 < elem2,
0
αν το elem1 == elem2 και
> 0
αν το elem1 > elem2.

Παράδειγμα

Το παρακάτω παράδειγμα διαβάζει μια γραμμή και την τυπώνει σύμφωνα με το διεθνές φωνητικό αλφάβητο (π.χ. για τη γραμμή HELLO WORLD θα τυπώσει:

Hotel
Echo
Lima
Lima
Oscar
Whiskey
Oscar
Romeo
Lima
Delta

/*
 * Read a line from the standard input and print it according to the
 * international phonetic alphabet.
 *
 * Diomidis Spinellis.  March 1999.
 *
 * $Id$
 *
 */

#include <stdlib.h>
#include <stdio.h>

/*
 * The international phonetic alphabet (sorted)
 */
char *names[] = {
	"Alpha",
	"Bravo",
	"Charlie",
	"Delta",
	"Echo",
	"Foxtrot",
	"Golf",
	"Hotel",
	"India",
	"Juliet",
	"Kilo",
	"Lima",
	"Mike",
	"November",
	"Oscar",
	"Papa",
	"Quebec",
	"Romeo",
	"Sierra",
	"Tango",
	"Uniform",
	"Victor",
	"Whiskey",
	"X-Ray",
	"Yankee",
	"Zulu",
};

/*
 * Bsearch compare function
 */
static int
namecmp(char **a, char **b)
{
	return (**a - **b);
}

main()
{
	char buff[80], *p, **name;

	fgets(buff, sizeof(buff), stdin);
	for (p = buff; *p; p++)
		if (name = (char **)bsearch(&p, names, 26, sizeof(char *), namecmp))
			printf("%s\n", *name, *name);
}