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