BinaryPlace - Maple Help

ListTools

 BinaryPlace
 perform a binary placement in a list

 Calling Sequence BinaryPlace(L, x, f, opt1, opt2, ...)

Parameters

 L - list, Vector, or one-dimensional Array x - anything f - (optional) procedure, operator, or algebraic expression opt1, opt2, ... - (optional) extra arguments to f

Description

 • The BinaryPlace(L, x) function performs a binary placement of x in L, where L is assumed to be sorted.  It returns the greatest index n such that L[n] precedes x. If x precedes all elements in a list L, then 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.
 • BinaryPlace also accepts a Vector or one-dimensional Array as its first argument. If x precedes all elements in an 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 L is a list, then the returned value $n$ is such that $\left[\mathrm{op}\left(1..n,L\right),x,\mathrm{op}\left(n+1..-1,L\right)\right]$ is still a sorted list. If L is a Vector or Array, then the returned value $n$ is such that $\left[\mathrm{op}\left(\mathrm{convert}\left({L}_{..n},\mathrm{list}\right)\right),x,\mathrm{op}\left(\mathrm{convert}\left({L}_{n+1..},\mathrm{list}\right)\right)\right]$ is sorted.
 • If three or more arguments are specified in the calling sequence, then $f\left(x,y,\mathrm{opt1},\mathrm{opt2},...\right)$ must return true if x precedes y.

Examples

 > $\mathrm{with}\left(\mathrm{ListTools}\right):$
 > $L≔\left[1,5,7,8,10\right]:$
 > $n≔\mathrm{BinaryPlace}\left(L,6\right)$
 ${n}{≔}{2}$ (1)
 > $\left[\mathrm{op}\left(1..n,L\right),6,\mathrm{op}\left(n+1..-1,L\right)\right]$
 $\left[{1}{,}{5}{,}{6}{,}{7}{,}{8}{,}{10}\right]$ (2)
 > $\mathrm{BinaryPlace}\left(\left["mac","made","magpie","mail"\right],"magic"\right)$
 ${2}$ (3)
 > $\mathrm{BinaryPlace}\left(\left[0,{\mathrm{sin}\left(1\right)}^{2},1\right],\mathrm{exp}\left(-\frac{1}{10}\right),\mathrm{verify},\mathrm{less_than}\right)$
 ${2}$ (4)
 > $\mathrm{BinaryPlace}\left(\left[\left\{4\right\},\left\{1,2,4\right\},\left\{1,2,3,4\right\}\right],\left\{2,4\right\},\mathrm{subset}\right)$
 ${1}$ (5)

An example with a reverse-sorted Array. Note that the eight elements of this 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)$
 ${A}{≔}\left[{173}{,}{157}{,}{101}{,}{21}{,}{17}{,}{-3}{,}{-33}{,}{-62}{,}{\text{⋯ -2 .. 5 Array}}\right]$ (6)

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

 > $\mathrm{BinaryPlace}\left(A,0,\mathrm{>}\right)$
 ${2}$ (7)

We find that the elements $-2$ up to $2$ are the positive ones, $3$ up to $5$ are negative.

 > $\mathrm{convert}\left(A\left[..2\right],'\mathrm{list}'\right)$
 $\left[{173}{,}{157}{,}{101}{,}{21}{,}{17}\right]$ (8)
 > $\mathrm{convert}\left(A\left[3..\right],'\mathrm{list}'\right)$
 $\left[{-3}{,}{-33}{,}{-62}\right]$ (9)

Compatibility

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