1 /*
2 * Copyright (c) 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * %sccs.include.redist.c%
6 */
7
8 #if defined(LIBC_SCCS) && !defined(lint)
9 static char sccsid[] = "@(#)bsearch.c 8.1 (Berkeley) 06/04/93";
10 #endif /* LIBC_SCCS and not lint */
11
12 #include <stddef.h>
13 #include <stdlib.h>
14
15 /*
16 * Perform a binary search.
17 *
18 * The code below is a bit sneaky. After a comparison fails, we
19 * divide the work in half by moving either left or right. If lim
20 * is odd, moving left simply involves halving lim: e.g., when lim
21 * is 5 we look at item 2, so we change lim to 2 so that we will
22 * look at items 0 & 1. If lim is even, the same applies. If lim
23 * is odd, moving right again involes halving lim, this time moving
24 * the base up one item past p: e.g., when lim is 5 we change base
25 * to item 3 and make lim 2 so that we will look at items 3 and 4.
26 * If lim is even, however, we have to shrink it by one before
27 * halving: e.g., when lim is 4, we still looked at item 2, so we
28 * have to make lim 3, then halve, obtaining 1, so that we will only
29 * look at item 3.
30 */
31 void *
bsearch(key,base0,nmemb,size,compar)32 bsearch(key, base0, nmemb, size, compar)
33 register const void *key;
34 const void *base0;
35 size_t nmemb;
36 register size_t size;
37 register int (*compar) __P((const void *, const void *));
38 {
39 register const char *base = base0;
40 register size_t lim;
41 register int cmp;
42 register const void *p;
43
44 for (lim = nmemb; lim != 0; lim >>= 1) {
45 p = base + (lim >> 1) * size;
46 cmp = (*compar)(key, p);
47 if (cmp == 0)
48 return ((void *)p);
49 if (cmp > 0) { /* key > p: move right */
50 base = (char *)p + size;
51 lim--;
52 } /* else move left */
53 }
54 return (NULL);
55 }
56