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