ListTools - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Programming : Data Types : Tables, lists, and sets : ListTools Package : ListTools/BinarySearch

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 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 fx,y returns true if x precedes y, or a list of the form [f1,opt1,opt2,...] such that f1x,y,opt1,opt2,... returns true if x precedes y.

• 

If g is specified in the calling sequence, it must be either a procedure or operator where gx,y returns true if x and y are equal, or a list of the form [g1,opt1,opt2,...] such that g1x,y,opt1,opt2,... returns true if x and y are equal.

  

If g is not included, boolean equality is used to test if two objects are equal.

Examples

withListTools:

BinarySearchseqithprimei&comma;i&equals;1..100&comma;89&comma;`<`

24

(1)

BinarySearchseqithprimei&comma;i&equals;1..100&comma;91&comma;`<`

0

(2)

BinarySearchmac&comma;made&comma;magic&comma;magpie&comma;mail&comma;main&comma;manor&comma;made

2

(3)

BinarySearch0&comma;sin12&comma;1&comma;1cos12&comma;verify&comma;less_than&comma;verify&comma;equal

2

(4)

BinarySearch4&comma;2&comma;4&comma;1&comma;2&comma;4&comma;1&comma;2&comma;3&comma;4&comma;2&comma;4&comma;`subset`

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.

AArray2..5&comma;173&comma;157&comma;101&comma;21&comma;17&comma;3&comma;33&comma;62

A:=Array2..5&comma;2&equals;173&comma;1&equals;157&comma;0&equals;101&comma;1&equals;21&comma;2&equals;17&comma;3&equals;3&comma;4&equals;33&comma;5&equals;62

(6)

By supplying `>` for f, we get BinaryPlace to understand the reverse ordering.

BinarySearchA&comma;0&comma;`>`

3

(7)

Since 0 doesn't occur in A, BinaryPlace returns the lowerbound of A minus one, that is, 3.

BinarySearchA&comma;17&comma;`>`

2

(8)

A2

17

(9)

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.

See Also

list

ListTools

ListTools[BinaryPlace]

sort

type/list

type/numeric

type/string

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam