View or download 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]
}
View or download 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 18868 days, 3 hours, 1 minutes ago.