binary_search

fn binary_search(Vec<int> xs, int needle) -> Option<int>

use collections::vec::{binary_search};

Finds needle in the ascending vector xs by halving, and returns an index holding it.

xs must be sorted (collections::sort does that); on an unsorted vector the result is unreliable. With duplicates, any matching index may be returned.

Parameters#

Returns#

Option<int>

Contracts#

Checked according to --contracts (see Contracts).

ensures found_at(xs, needle, result)

Examples#

use collections::vec::{binary_search};
use tests::assert;
let xs: Vec<int> = [1, 3, 5, 7, 9];
assert!((binary_search(xs, 7) ?? -1) == 3);
assert!(binary_search(xs, 4).is_none());

See also#

• collections::sort
• fold_int: The same as fold; kept for older code.
• contains: Returns true when needle is in xs.
• index_of: Returns the index of the first needle in xs, or -1.
• dedup: Returns xs with runs of equal neighbours collapsed to one value.
• map: Returns a new vector with mapper applied to each element, in order.
• filter: Returns the elements for which pred is true, in order.
• first: Returns the first element, or None when xs is empty.