1 | /* |
---|
2 | * bsearch.c |
---|
3 | * Original Author: G. Haley |
---|
4 | * Rewritten by: G. Noer |
---|
5 | * |
---|
6 | * Searches an array of nmemb members, the initial member of which is pointed |
---|
7 | * to by base, for a member that matches the object pointed to by key. The |
---|
8 | * contents of the array shall be in ascending order according to a comparison |
---|
9 | * function pointed to by compar. The function shall return an integer less |
---|
10 | * than, equal to or greater than zero if the first argument is considered to be |
---|
11 | * respectively less than, equal to or greater than the second. Returns a |
---|
12 | * pointer to the matching member of the array, or a null pointer if no match |
---|
13 | * is found. |
---|
14 | */ |
---|
15 | |
---|
16 | /* |
---|
17 | FUNCTION |
---|
18 | <<bsearch>>---binary search |
---|
19 | |
---|
20 | INDEX |
---|
21 | bsearch |
---|
22 | |
---|
23 | SYNOPSIS |
---|
24 | #include <stdlib.h> |
---|
25 | void *bsearch(const void *<[key]>, const void *<[base]>, |
---|
26 | size_t <[nmemb]>, size_t <[size]>, |
---|
27 | int (*<[compar]>)(const void *, const void *)); |
---|
28 | |
---|
29 | DESCRIPTION |
---|
30 | <<bsearch>> searches an array beginning at <[base]> for any element |
---|
31 | that matches <[key]>, using binary search. <[nmemb]> is the element |
---|
32 | count of the array; <[size]> is the size of each element. |
---|
33 | |
---|
34 | The array must be sorted in ascending order with respect to the |
---|
35 | comparison function <[compar]> (which you supply as the last argument of |
---|
36 | <<bsearch>>). |
---|
37 | |
---|
38 | You must define the comparison function <<(*<[compar]>)>> to have two |
---|
39 | arguments; its result must be negative if the first argument is |
---|
40 | less than the second, zero if the two arguments match, and |
---|
41 | positive if the first argument is greater than the second (where |
---|
42 | ``less than'' and ``greater than'' refer to whatever arbitrary |
---|
43 | ordering is appropriate). |
---|
44 | |
---|
45 | RETURNS |
---|
46 | Returns a pointer to an element of <[array]> that matches <[key]>. If |
---|
47 | more than one matching element is available, the result may point to |
---|
48 | any of them. |
---|
49 | |
---|
50 | PORTABILITY |
---|
51 | <<bsearch>> is ANSI. |
---|
52 | |
---|
53 | No supporting OS subroutines are required. |
---|
54 | */ |
---|
55 | |
---|
56 | #include <stdlib.h> |
---|
57 | |
---|
58 | void * |
---|
59 | bsearch (const void *key, |
---|
60 | const void *base, |
---|
61 | size_t nmemb, |
---|
62 | size_t size, |
---|
63 | int (*compar) (const void *, const void *)) |
---|
64 | { |
---|
65 | void *current; |
---|
66 | size_t lower = 0; |
---|
67 | size_t upper = nmemb; |
---|
68 | size_t index; |
---|
69 | int result; |
---|
70 | |
---|
71 | if (nmemb == 0 || size == 0) |
---|
72 | return NULL; |
---|
73 | |
---|
74 | while (lower < upper) |
---|
75 | { |
---|
76 | index = (lower + upper) / 2; |
---|
77 | current = (void *) (((char *) base) + (index * size)); |
---|
78 | |
---|
79 | result = compar (key, current); |
---|
80 | |
---|
81 | if (result < 0) |
---|
82 | upper = index; |
---|
83 | else if (result > 0) |
---|
84 | lower = index + 1; |
---|
85 | else |
---|
86 | return current; |
---|
87 | } |
---|
88 | |
---|
89 | return NULL; |
---|
90 | } |
---|
91 | |
---|