ListTools
BinarySearch
perform a binary search on a list
Calling Sequence
Parameters
Description
Examples
Compatibility
BinarySearch(L, x, f, g)
L
-
list, Vector, or one-dimensional Array
x
anything
f
(optional) procedure, operator, algebraic expression, or list
g
The BinarySearch(L, x) function performs binary search on L for element x, where L is assumed to be sorted. If a match is found, the position of the element is returned; otherwise, if L is a list, the value is returned.
In this form of the calling sequence, x must be of type numeric or string and L should contain values of the same type in ascending order.
BinarySearch also accepts a Vector or one-dimensional Array as its first argument. If x does not occur in a given Array, then the value that is returned is the lowerbound of the Array minus one. Since Vectors, like lists, always have a lowerbound of 1, the value returned for a Vector in this case is .
If parameter f is specified in the calling sequence, it must be either a procedure or operator where returns true if x precedes y, or a list of the form such that returns true if x precedes y.
If g is specified in the calling sequence, it must be either a procedure or operator where returns true if x and y are equal, or a list of the form such that returns true if x and y are equal.
If g is not included, boolean equality is used to test if two objects are equal.
BinarySearch searches for an exact match. To instead look for where a value would fit if it was inserted into the list, see BinaryPlace.
An example with a reverse-sorted Array. Note that the eight elements of the Array are indexed with the numbers up to .
By supplying for f, we get BinarySearch to understand the reverse ordering.
Since does not occur in , BinarySearch returns the lowerbound of A minus one, that is, .
The index of in is .
The ListTools[BinarySearch] command was updated in Maple 18.
The L parameter was updated in Maple 18.
See Also
list
ListTools[BinaryPlace]
sort
type/list
type/numeric
type/string
Download Help Document