perform a binary search on a list
BinarySearch(L, x, f, g)
list, Vector, or one-dimensional Array
(optional) procedure, operator, algebraic expression, or list
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 0 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 0.
If parameter f is specified in the calling sequence, it must be either a procedure or operator where f⁡x,y returns true if x precedes y, or a list of the form [f1,opt1,opt2,...] such that f1⁡x,y,opt1,opt2,... returns true if x precedes y.
If g is specified in the calling sequence, it must be either a procedure or operator where g⁡x,y returns true if x and y are equal, or a list of the form [g1,opt1,opt2,...] such that g1⁡x,y,opt1,opt2,... 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 −2 up to 5.
A ≔ Array⁡−2..5,173,157,101,21,17,−3,−33,−62
By supplying `>` for f, we get BinarySearch to understand the reverse ordering.
Since 0 does not occur in A, BinarySearch returns the lowerbound of A minus one, that is, −3.
The index of 17 in A is 2.
The ListTools[BinarySearch] command was updated in Maple 18.
The L parameter was updated in Maple 18.
Download Help Document