Download or view binarySearch.frink in plain text format
// This is an algorithm for doing binary search of a list in Frink.
//
// This is now obsolete. The class OrderedList in Frink will do this
// for you and contains a .binarySearch method.
//
// arguments:
// list: an ordered list of items
//
// item: the item to search for in the list
//
// orderFunction: a two-argument function of the form {|a,b| ... } where
// the function returns -1 if a<b, 0 if a==b, and 1 if a > b
// (such as the <=> operator returns. This is the default
// comparison if no order function is passed in.)
//
// This returns the index of the item to insert *before* (for example,
// using the method list.insert[pos, item] ) to put the item in the right
// order. If the item is found anywhere in the list, this returns the index
// of the matching item in the list. If the item is not found in the
// list, this still returns the index before which it should be inserted.
binarySearch[list, item, orderFunction = {|a,b| a <=> b}] :=
{
start = 0
end = length[list] - 1
var current
var comp
while (start <= end)
{
current = (end + start) div 2
comp = orderFunction[item, list@current]
if comp == 0
return current
if (comp == -1)
end = current - 1
else
start = current + 1
}
return start
}
/** This is a function that tries to find a single local extreme of a function.
It uses a binary search routine.
args:
[f, xmin, xmax, minxstep, multiplier]
where:
f is a function that takes one argument for x and returns a single value.
xmin is the minimum of the range to search
xmax is the maximum of the range to search
minxstep is the smallest x step to take.
multiplier is 1 to find minimum, -1 to find maximum.
*/
findAnExtreme[f, xmin, xmax, minxstep, multiplier] :=
{
do
{
// We use this formulation so it works with dates.
mid = xmin + (xmax - xmin) / 2
fmin = f[xmin] multiplier
fmax = f[xmax] multiplier
if fmin < fmax
xmax = mid
else
xmin = mid
} while xmax - xmin > minxstep
if fmin<fmax
return [xmin, fmin multiplier]
else
return [xmax, fmax multiplier]
}
/** This is a function that tries to find a single local minimum of a function.
It uses a binary search routine.
args:
[f, xmin, xmax, minxstep]
where:
f is a function that takes one argument for x and returns a single value.
xmin is the minimum of the range to search
xmax is the maximum of the range to search
minxstep is the smallest x step to take.
*/
findALocalMinimum[f, xmin, xmax, minxstep] :=
{
return findAnExtreme[f, xmin, xmax, minxstep, 1]
}
/** This is a function that tries to find a single local maximum of a function.
It uses a binary search routine.
args:
[f, xmin, xmax, minxstep]
where:
f is a function that takes one argument for x and returns a single value.
xmin is the minimum of the range to search
xmax is the maximum of the range to search
minxstep is the smallest x step to take.
*/
findALocalMaximum[f, xmin, xmax, minxstep] :=
{
return findAnExtreme[f, xmin, xmax, minxstep, -1]
}
Download or view binarySearch.frink in plain text format
This is a program written in the programming language Frink.
For more information, view the Frink
Documentation or see More Sample Frink Programs.
Alan Eliasen was born 19346 days, 23 hours, 23 minutes ago.