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) | |
855e35a8 | 9 | static char sccsid[] = "@(#)bsearch.c 5.2 (Berkeley) %G%"; |
bc5feef1 KB |
10 | #endif /* LIBC_SCCS and not lint */ |
11 | ||
855e35a8 | 12 | #include <stddef.h> /* size_t */ |
bc5feef1 | 13 | |
855e35a8 KB |
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; | |
bc5feef1 KB |
34 | size_t nmemb; |
35 | register size_t size; | |
36 | register int (*compar)(); | |
37 | { | |
855e35a8 KB |
38 | register char *base = base0; |
39 | register int lim, cmp; | |
40 | register void *p; | |
bc5feef1 | 41 | |
855e35a8 KB |
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 */ | |
bc5feef1 | 51 | } |
855e35a8 | 52 | return (NULL); |
bc5feef1 | 53 | } |