![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to bsearch CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / a / usr / man / MULTI|
Return to bsearch CVS log | Up to [MW Coherent from dump] / coherent / a / usr / man / MULTI |
1.1 root 1:
2:
3: bsearch() General Function bsearch()
4:
5:
6:
7:
8: Search an array
9:
10: #iinncclluuddee <ssttddlliibb.hh>
11: cchhaarr *bbsseeaarrcchh(_k_e_y, _a_r_r_a_y, _n_u_m_b_e_r, _s_i_z_e, _c_o_m_p_a_r_i_s_o_n)
12: cchhaarr *_k_e_y, *_a_r_r_a_y;
13: ssiizzee_tt _n_u_m_b_e_r, _s_i_z_e;
14: iinntt (*_c_o_m_p_a_r_i_s_o_n)();
15:
16: bbsseeaarrcchh searches a sorted array for a given item. _i_t_e_m points to
17: the object sought. _a_r_r_a_y points to the base of the array; it has
18: _n_u_m_b_e_r elements, each of which is _s_i_z_e bytes long. Its elements
19: must be sorted into ascending order before it is searched by
20: bbsseeaarrcchh.
21:
22: _c_o_m_p_a_r_i_s_o_n points to the function that compares array elements.
23: _c_o_m_p_a_r_i_s_o_n must return zero if its arguments match, a number
24: greater than zero if the element pointed to by _a_r_g_1 is greater
25: than the element pointed to by _a_r_g_2, and a number less than zero
26: if the element pointed to by _a_r_g_1 is less than the element
27: pointed to by _a_r_g_2.
28:
29: bbsseeaarrcchh returns a pointer to the array element that matches _i_t_e_m.
30: If no element matches _i_t_e_m, then bbsseeaarrcchh returns NULL. If more
31: than one element within _a_r_r_a_y matches _i_t_e_m, which element is
32: matched is unspecified.
33:
34: ***** Example *****
35:
36: This example uses bbsseeaarrcchh to translate English into ``bureaucrat-
37: ese''.
38:
39:
40: #include <stdio.h>
41: #include <stdlib.h>
42: #include <string.h>
43:
44:
45:
46: struct syntab {
47: char *english, *bureaucratic;
48: } cdtab[] = {
49: /* The left column is in alphabetical order */
50:
51:
52:
53: "affect", "impact",
54: "after", "subsequent to",
55: "building","physical facility",
56: "call", "refer to as",
57: "do", "implement",
58:
59:
60:
61:
62:
63:
64: COHERENT Lexicon Page 1
65:
66:
67:
68:
69: bsearch() General Function bsearch()
70:
71:
72:
73: "false", "inoperative",
74: "finish", "finalize",
75: "first", "initial",
76: "full", "in-depth",
77: "help", "facilitate",
78:
79:
80:
81: "kill", "terminate",
82: "lie", "inoperative statement",
83: "order", "prioritize",
84: "talk", "interpersonal communication",
85: "then", "at that point in time",
86: "use", "utilize"
87: };
88:
89:
90:
91: int
92: comparator(key, item)
93: char *key;
94: struct syntab *item;
95: {
96: return(strcmp(key, item->english));
97: }
98:
99:
100:
101: main()
102: {
103: struct syntab *ans;
104: char buf[80];
105:
106:
107:
108: for(;;) {
109: printf("Enter an English word: ");
110: fflush(stdout);
111:
112:
113:
114: if(gets(buf) || !strcmp(buf, "quit") == NULL)
115: break;
116:
117:
118:
119: if((ans = bsearch(buf, (char *)cdtab,
120: sizeof(cdtab)/ sizeof(struct syntab),
121: sizeof(struct syntab),
122: comparator)) == NULL)
123: printf("%s not found\n");
124:
125:
126:
127:
128:
129:
130: COHERENT Lexicon Page 2
131:
132:
133:
134:
135: bsearch() General Function bsearch()
136:
137:
138:
139: else
140: printf("Don't say \"%s\"; say \"%s\"!\n",
141: ans->english, ans->bureaucratic);
142: }
143: }
144:
145:
146: ***** See Also *****
147:
148: ggeenneerraall ffuunnccttiioonnss, qqssoorrtt(), ssttddlliibb.hh
149:
150: ***** Notes *****
151:
152: The name bbsseeaarrcchh implies that this function performs a binary
153: search. A binary search looks at the midpoint of the array, and
154: compares it with the element being sought. If that element
155: matches, then the work is done. If it does not, then bbsseeaarrcchh
156: checks the midpoint of either the upper half of the array or of
157: the lower half, depending upon whether the midpoint of the array
158: is larger or smaller than the item being sought. bbsseeaarrcchh bisects
159: smaller and smaller regions of the array until it either finds a
160: match or can bisect no further.
161:
162: It is important that the input _a_r_r_a_y be sorted, or bbsseeaarrcchh will
163: not function correctly.
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196: COHERENT Lexicon Page 3
197:
198:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.