-
Notifications
You must be signed in to change notification settings - Fork 17
/
hunt.c
118 lines (95 loc) · 3.14 KB
/
hunt.c
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/* ------- file: -------------------------- hunt.c ------------------
Version: rh2.0
Author: Han Uitenbroek ([email protected])
Last modified: Tue Feb 16 14:40:59 1999 --
-------------------------- ----------RH-- */
/* --- Find index of value in array (cf., Num. Recipes, p 91).
Use previous value of ilow to hunt up or down list and bracket value.
-- -------------- */
#include "rh.h"
/* ------- begin -------------------------- Hunt.c ------------------ */
void Hunt(int n, double *array, double value, int *ilow)
{
bool_t ascend;
int ihigh, index, increment;
ascend = (array[n-1] > array[0]) ? TRUE : FALSE;
if ((*ilow <= 0) || (*ilow > n-1)) {
/* --- Input guess not useful here, go to bisection -- --------- */
*ilow = 0;
ihigh = n;
} else {
/* --- Else hunt up or down to bracket value -- -------------- */
increment = 1;
if (((value >= array[*ilow]) ? TRUE : FALSE) == ascend) {
ihigh = *ilow + increment;
if (*ilow == n-1) return;
/* --- Hunt up -- -------------- */
while (((value >= array[ihigh]) ? TRUE : FALSE) == ascend) {
*ilow = ihigh;
increment += increment;
ihigh = *ilow + increment;
if (ihigh >= n) { ihigh = n; break; }
}
} else {
ihigh = *ilow;
if (*ilow == 0) return;
/* --- Hunt down -- -------------- */
while (((value <= array[*ilow]) ? TRUE : FALSE) == ascend) {
ihigh = *ilow;
increment += increment;
*ilow = ihigh - increment;
if (*ilow <= 0) { *ilow = 0; break; }
}
}
}
/* --- Bisection algorithm -- -------------- */
if (ascend) {
while (ihigh - *ilow > 1) {
index = (ihigh + *ilow) >> 1;
if (value >= array[index])
*ilow = index;
else
ihigh = index;
}
} else {
while (ihigh - *ilow > 1) {
index = (ihigh + *ilow) >> 1;
if (value <= array[index])
*ilow = index;
else
ihigh = index;
}
}
}
/* ------- end ---------------------------- Hunt.c ------------------ */
/* ---------------------------------------- Locate.c ---------------- */
/* --- Find index of value in array (cf., Num. Recipes, p 90).
Note: The Num. Recipes routine does not give the correct index
for values that are exactly equal to an array value!
-- -------------- */
/* ------- begin -------------------------- Locate.c ---------------- */
void Locate(int n, double *array, double value, int *ilow)
{
bool_t ascend;
int ihigh, index;
ascend = (array[n-1] > array[0]) ? TRUE : FALSE;
*ilow = 0; ihigh = n;
if (ascend) {
while (ihigh - *ilow > 1) {
index = (ihigh + *ilow) >> 1;
if (value >= array[index])
*ilow = index;
else
ihigh = index;
}
} else {
while (ihigh - *ilow > 1) {
index = (ihigh + *ilow) >> 1;
if (value <= array[index])
*ilow = index;
else
ihigh = index;
}
}
}
/* ------- end ---------------------------- Locate.c ---------------- */