|
Calling Sequence
|
|
BinarySearch(L, x, f, g)
|
|
Parameters
|
|
L
|
-
|
list, Vector, or one-dimensional Array
|
x
|
-
|
anything
|
f
|
-
|
(optional) procedure, operator, algebraic expression, or list
|
g
|
-
|
(optional) procedure, operator, algebraic expression, or list
|
|
|
|
|
Description
|
|
•
|
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.
|
|
|
Examples
|
|
>
|
|
>
|
|
>
|
|
>
|
|
>
|
|
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 .
|
|
Compatibility
|
|
•
|
The ListTools[BinarySearch] command was updated in Maple 18.
|
•
|
The L parameter was updated in Maple 18.
|
|
|
|