BinarySearch - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


ListTools

  

BinarySearch

  

perform a binary search on a list

 

Calling Sequence

Parameters

Description

Examples

Compatibility

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

(1)

(2)

(3)

(4)

(5)

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.

(6)

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

(7)

(8)

The index of  in  is .

Compatibility

• 

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

• 

The L parameter was updated in Maple 18.

See Also

list

ListTools

ListTools[BinaryPlace]

sort

type/list

type/numeric

type/string

 


Download Help Document