BinarySearch - Maple Help

ListTools

 BinarySearch
 perform a binary search on a list

 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 $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\left(x,y\right)$ returns true if x precedes y, or a list of the form $[\mathrm{f1},\mathrm{opt1},\mathrm{opt2},...]$ such that $\mathrm{f1}\left(x,y,\mathrm{opt1},\mathrm{opt2},...\right)$ returns true if x precedes y.
 • If g is specified in the calling sequence, it must be either a procedure or operator where $g\left(x,y\right)$ returns true if x and y are equal, or a list of the form $[\mathrm{g1},\mathrm{opt1},\mathrm{opt2},...]$ such that $\mathrm{g1}\left(x,y,\mathrm{opt1},\mathrm{opt2},...\right)$ 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

 > $\mathrm{with}\left(\mathrm{ListTools}\right):$
 > $\mathrm{BinarySearch}\left(\left[\mathrm{seq}\left(\mathrm{ithprime}\left(i\right),i=1..100\right)\right],89,\mathrm{<}\right)$
 ${24}$ (1)
 > $\mathrm{BinarySearch}\left(\left[\mathrm{seq}\left(\mathrm{ithprime}\left(i\right),i=1..100\right)\right],91,\mathrm{<}\right)$
 ${0}$ (2)
 > $\mathrm{BinarySearch}\left(\left["mac","made","magic","magpie","mail","main","manor"\right],"made"\right)$
 ${2}$ (3)
 > $\mathrm{BinarySearch}\left(\left[0,{\mathrm{sin}\left(1\right)}^{2},1\right],1-{\mathrm{cos}\left(1\right)}^{2},\left[\mathrm{verify},\mathrm{less_than}\right],\left[\mathrm{verify},\mathrm{equal}\right]\right)$
 ${2}$ (4)
 > $\mathrm{BinarySearch}\left(\left[\left\{4\right\},\left\{2,4\right\},\left\{1,2,4\right\},\left\{1,2,3,4\right\}\right],\left\{2,4\right\},\mathrm{subset}\right)$
 ${2}$ (5)

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≔\mathrm{Array}\left(-2..5,\left[173,157,101,21,17,-3,-33,-62\right]\right)$

By supplying $\mathrm{>}$ for f, we get BinarySearch to understand the reverse ordering.

 > $\mathrm{BinarySearch}\left(A,0,\mathrm{>}\right)$
 ${-3}$ (6)

Since $0$ does not occur in $A$, BinarySearch returns the lowerbound of A minus one, that is, $-3$.

 > $\mathrm{BinarySearch}\left(A,17,\mathrm{>}\right)$
 ${2}$ (7)
 > ${A}_{2}$
 ${17}$ (8)

The index of $17$ in $A$ is $2$.

Compatibility

 • The ListTools[BinarySearch] command was updated in Maple 18.
 • The L parameter was updated in Maple 18.