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 * 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