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.

$\mathrm{with}\left(\mathrm{ListTools}\right)\:$

$\mathrm{BinarySearch}\left(\left[\mathrm{seq}\left(\mathrm{ithprime}\left(i\right)\&comma;i=1..100\right)\right]\&comma;89\&comma;\mathrm{`<`}\right)$

$24$

$\mathrm{BinarySearch}\left(\left[\mathrm{seq}\left(\mathrm{ithprime}\left(i\right)\&comma;i=1..100\right)\right]\&comma;91\&comma;\mathrm{`<`}\right)$

$0$

$\mathrm{BinarySearch}\left(\left[''mac''\&comma;''made''\&comma;''magic''\&comma;''magpie''\&comma;''mail''\&comma;''main''\&comma;''manor''\right]\&comma;''made''\right)$

$2$

$\mathrm{BinarySearch}\left(\left[0\&comma;{\sin \left(1\right)}^2\&comma;1\right]\&comma;1-{\cos \left(1\right)}^2\&comma;\left[\mathrm{verify}\&comma;\mathrm{less\_than}\right]\&comma;\left[\mathrm{verify}\&comma;\mathrm{equal}\right]\right)$

$2$

$\mathrm{BinarySearch}\left(\left[\left\{4\right\}\&comma;\left\{2\&comma;4\right\}\&comma;\left\{1\&comma;2\&comma;4\right\}\&comma;\left\{1\&comma;2\&comma;3\&comma;4\right\}\right]\&comma;\left\{2\&comma;4\right\}\&comma;\mathrm{`subset`}\right)$

$2$

$A≔\mathrm{Array}\left(-2..5\&comma;\left[173\&comma;157\&comma;101\&comma;21\&comma;17\&comma;-3\&comma;-33\&comma;-62\right]\right)$

$A≔\left[173\&comma;157\&comma;101\&comma;21\&comma;17\&comma;\mathrm{-3}\&comma;\mathrm{-33}\&comma;\mathrm{-62}\&comma;\text{⋯ -2 .. 5 Array}\right]$

$\mathrm{BinarySearch}\left(A\&comma;0\&comma;\mathrm{`>`}\right)$

$\mathrm{-3}$

$\mathrm{BinarySearch}\left(A\&comma;17\&comma;\mathrm{`>`}\right)$

$2$

$A\left[2\right]$

$17$

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

The L parameter was updated in Maple 18.