* Copyright (c) 1990 Regents of the University of California.
* %sccs.include.redist.c%
#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid
[] = "@(#)bsearch.c 5.3 (Berkeley) %G%";
#endif /* LIBC_SCCS and not lint */
#include <stddef.h> /* size_t */
* Perform a binary search.
* The code below is a bit sneaky. After a comparison fails, we
* divide the work in half by moving either left or right. If lim
* is odd, moving left simply involves halving lim: e.g., when lim
* is 5 we look at item 2, so we change lim to 2 so that we will
* look at items 0 & 1. If lim is even, the same applies. If lim
* is odd, moving right again involes halving lim, this time moving
* the base up one item past p: e.g., when lim is 5 we change base
* to item 3 and make lim 2 so that we will look at items 3 and 4.
* If lim is even, however, we have to shrink it by one before
* halving: e.g., when lim is 4, we still looked at item 2, so we
* have to make lim 3, then halve, obtaining 1, so that we will only
bsearch(key
, base0
, nmemb
, size
, compar
)
register int (*compar
)();
register char *base
= base0
;
for (lim
= nmemb
; lim
!= 0; lim
>>= 1) {
p
= base
+ (lim
>> 1) * size
;
if (cmp
> 0) { /* key > p: move right */