binsearch.html
5.57 KB
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><title>R: Binary Search</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<link rel="stylesheet" type="text/css" href="../../R.css">
</head><body>
<table width="100%" summary="page for binsearch {gtools}"><tr><td>binsearch {gtools}</td><td align="right">R Documentation</td></tr></table>
<h2>Binary Search</h2>
<h3>Description</h3>
<p>
Search within a specified range to locate an integer parameter which
results in the the specified monotonic function obtaining a given value.
</p>
<h3>Usage</h3>
<pre>
binsearch(fun, range, ..., target = 0, lower = ceiling(min(range)),
upper = floor(max(range)), maxiter = 100, showiter = FALSE)
</pre>
<h3>Arguments</h3>
<table summary="R argblock">
<tr valign="top"><td><code>fun</code></td>
<td>
Monotonic function over which the search will be performed.</td></tr>
<tr valign="top"><td><code>range</code></td>
<td>
2-element vector giving the range for the search.</td></tr>
<tr valign="top"><td><code>...</code></td>
<td>
Additional parameters to the function <code>fun</code>.</td></tr>
<tr valign="top"><td><code>target</code></td>
<td>
Target value for <code>fun</code>. Defaults to 0.</td></tr>
<tr valign="top"><td><code>lower</code></td>
<td>
Lower limit of search range. Defaults to <code>min(range)</code>.</td></tr>
<tr valign="top"><td><code>upper</code></td>
<td>
Upper limit of search range. Defaults to <code>max(range)</code>.</td></tr>
<tr valign="top"><td><code>maxiter</code></td>
<td>
Maximum number of search iterations. Defaults to 100.</td></tr>
<tr valign="top"><td><code>showiter</code></td>
<td>
Boolean flag indicating whether the algorithm state
should be printed at each iteration. Defaults to FALSE.</td></tr>
</table>
<h3>Details</h3>
<p>
This function implements an extension to the standard binary search
algorithm for searching a sorted list. The algorithm has been
extended to cope with cases where an exact match is not possible, to
detect whether that the function may be monotonic increasing or
decreasing and act appropriately, and to detect when the target value
is outside the specified range.
</p>
<p>
The algorithm initializes two variable <code>lo</code> and
<code>high</code> to the extremes values of <code>range</code>. It then generates
a new value <code>center</code> halfway between <code>lo</code> and <code>hi</code>. If
the value of <code>fun</code> at <code>center</code> exceeds <code>target</code>, it
becomes the new value for <code>lo</code>, otherwise it becomes the new
value for <code>hi</code>. This process is iterated until <code>lo</code> and
<code>hi</code> are adjacent. If the function at one or the other equals
the target, this value is returned, otherwise <code>lo</code>, <code>hi</code>,
and the function value at both are returned.
</p>
<p>
Note that when the specified target value falls between integers, the
em{two} closest values are returned. If the specified target falls
outside of the specified <code>range</code>, the closest endpoint of the
range will be returned, and an warning message will be generated. If
the maximum number if iterations was reached, the endpoints of the
current subset of the range under consideration will be returned.
</p>
<h3>Value</h3>
<p>
A list containing:
</p>
<table summary="R argblock">
<tr valign="top"><td><code>call</code></td>
<td>
How the function was called.</td></tr>
<tr valign="top"><td><code>numiter</code></td>
<td>
The number of iterations performed</td></tr>
<tr valign="top"><td><code>flag </code></td>
<td>
One of the strings, "Found", "Between Elements",
"Maximum number of iterations reached", "Reached lower boundary", or
"Reached upper boundary."</td></tr>
<tr valign="top"><td><code>where</code></td>
<td>
One or two values indicating where the search
terminated.</td></tr>
<tr valign="top"><td><code>value</code></td>
<td>
Value of the function <code>fun</code> at the values of
<code>where</code>.</td></tr>
</table>
<h3>Note</h3>
<p>
This function often returns two values for <code>where</code> and
<code>value</code>. Be sure to check the <code>flag</code> parameter to see what
these values mean.
</p>
<h3>Author(s)</h3>
<p>
Gregory R. Warnes <a href="mailto:warnes@bst.rochester.edu">warnes@bst.rochester.edu</a>
</p>
<h3>See Also</h3>
<p>
<code><a href="../../base/html/optim.html">optim</a></code>, <code><a href="../../base/html/optimize.html">optimize</a></code>,
<code><a href="../../base/html/uniroot.html">uniroot</a></code>
</p>
<h3>Examples</h3>
<pre>
### Toy examples
# search for x=10
binsearch( function(x) x-10, range=c(0,20) )
# search for x=10.1
binsearch( function(x) x-10.1, range=c(0,20) )
### Classical toy example
# binary search for the index of 'M' among the sorted letters
fun <- function(X) ifelse(LETTERS[X] > 'M', 1,
ifelse(LETTERS[X] < 'M', -1, 0 ) )
binsearch( fun, range=1:26 )
# returns $where=13
LETTERS[13]
### Substantive example, from genetics
## Not run:
library(genetics)
# Determine the necessary sample size to detect all alleles with
# frequency 0.07 or greater with probability 0.95.
power.fun <- function(N) 1 - gregorius(N=N, freq=0.07)$missprob
binsearch( power.fun, range=c(0,100), target=0.95 )
# equivalent to
gregorius( freq=0.07, missprob=0.05)
## End(Not run)
</pre>
<hr><div align="center">[Package <em>gtools</em> version 2.4.0 <a href="00Index.html">Index]</a></div>
</body></html>