Commit | Line | Data |
---|---|---|
bc5feef1 | 1 | /* |
855e35a8 | 2 | * Copyright (c) 1990 Regents of the University of California. |
bc5feef1 KB |
3 | * All rights reserved. |
4 | * | |
855e35a8 | 5 | * %sccs.include.redist.c% |
bc5feef1 KB |
6 | */ |
7 | ||
8 | #if defined(LIBC_SCCS) && !defined(lint) | |
f0a345ab | 9 | static char sccsid[] = "@(#)bsearch.c 5.4 (Berkeley) %G%"; |
bc5feef1 KB |
10 | #endif /* LIBC_SCCS and not lint */ |
11 | ||
855e35a8 | 12 | #include <stddef.h> /* size_t */ |
dd967b02 | 13 | #include <stdlib.h> |
bc5feef1 | 14 | |
855e35a8 KB |
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) | |
f0a345ab DS |
33 | register const void *key; |
34 | const void *base0; | |
bc5feef1 KB |
35 | size_t nmemb; |
36 | register size_t size; | |
f0a345ab | 37 | register int (*compar) __P((const void *, const void *)); |
bc5feef1 | 38 | { |
f0a345ab | 39 | register const char *base = base0; |
855e35a8 | 40 | register int lim, cmp; |
f0a345ab | 41 | register const void *p; |
bc5feef1 | 42 | |
855e35a8 KB |
43 | for (lim = nmemb; lim != 0; lim >>= 1) { |
44 | p = base + (lim >> 1) * size; | |
45 | cmp = (*compar)(key, p); | |
46 | if (cmp == 0) | |
f0a345ab | 47 | return ((void *)p); |
855e35a8 KB |
48 | if (cmp > 0) { /* key > p: move right */ |
49 | base = (char *)p + size; | |
50 | lim--; | |
51 | } /* else move left */ | |
bc5feef1 | 52 | } |
855e35a8 | 53 | return (NULL); |
bc5feef1 | 54 | } |