1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
/*
* Motif Tools Library, Version 3.1
* $Id$
*
* Written by David Flanagan.
* Copyright (c) 1992-2001 by David Flanagan.
* All Rights Reserved. See the file COPYRIGHT for details.
* This is open source software. See the file LICENSE for details.
* There is no warranty for this software. See NO_WARRANTY for details.
*
* $Log$
* Revision 1.1.1.1 2001/07/18 11:06:01 root
* Initial checkin.
*
* Revision 1.1 2001/06/12 15:00:21 andre
* AA-2001-06-12-0: replaced Xmt212 by Xmt310
* (http://sourceforge.net/projects/motiftools) with
* our xmt212 patches applied
*
*
*/
#include <Xmt/Xmt.h>
#if NeedFunctionPrototypes
int XmtBSearch(StringConst target, String *list, int num)
#else
int XmtBSearch(target, list, num)
StringConst target;
String *list;
int num;
#endif
{
int half = num/2;
int result;
/* do a linear search if there aren't may keywords left */
/* avoids the overhead of recursion */
if (num <= 4) {
for(num--; num >= 0; num--)
if (strcmp(target, list[num]) == 0) break;
return num;
}
/* otherwise do a binary search */
result = strcmp(target, list[half]);
if (result == 0) return half;
else if (result < 0)
return XmtBSearch(target, list, half);
else {
result = XmtBSearch(target, &list[half+1], num-half-1);
if (result != -1) result += half+1;
return result;
}
}
|
