Binary Search
Find a value’s index in a sorted array by repeatedly halving the range it could be in.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: binary_search.nomi
//# Binary search for a value in a sorted vector.
/// The index of `value` in `items`, which must be sorted, found by halving
/// the range it could be in.
pub fn find<T>(items: Vector<T>, value: T) -> Result<Int, String> where T: Comparable
search(items, value, 0, Vector.length(items))
end
/// Searches the indices from `low` up to, not including, `high`.
fn search<T>(
items: Vector<T>,
value: T,
low: Int,
high: Int,
) -> Result<Int, String> where T: Comparable
if low >= high then return Err("value not in array")
middle = (low + high) / 2
item = Vector.get(items, middle)!
case Comparable.compare(value, item)
.Less -> search(items, value, low, middle)
.Equal -> Ok(middle)
.Greater -> search(items, value, middle + 1, high)
end
end
// FILE: binary_search_test.nomi
import binary_search
test "finds a value"
[
("finds a value in an array with one element", Vector[6], 6, 0),
("finds a value in the middle of an array", Vector[1, 3, 4, 6, 8, 9, 11], 6, 3),
("finds a value at the beginning of an array", Vector[1, 3, 4, 6, 8, 9, 11], 1, 0),
("finds a value at the end of an array", Vector[1, 3, 4, 6, 8, 9, 11], 11, 6),
(
"finds a value in an array of odd length",
Vector[1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 634],
144,
9,
),
(
"finds a value in an array of even length",
Vector[1, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377],
21,
5,
),
]
|> subtests (description, items, value, expected), description
assert binary_search.find(items, value) == Ok(expected)
end
end
test "reports a missing value"
[
("identifies that a value is not included in the array", Vector[1, 3, 4, 6, 8, 9, 11], 7),
(
"a value smaller than the array's smallest value is not found",
Vector[1, 3, 4, 6, 8, 9, 11],
0,
),
(
"a value larger than the array's largest value is not found",
Vector[1, 3, 4, 6, 8, 9, 11],
13,
),
("nothing is found in an empty array", Vector[], 1),
("nothing is found when the left and right bounds cross", Vector[1, 2], 0),
]
|> subtests (description, items, value), description
assert binary_search.find(items, value) == Err("value not in array")
end
endok finds a value (6 cases)
ok reports a missing value (5 cases)
test result: ok. 11 passed, 0 failed
How it’s written
Section titled “How it’s written”- The input is a
Vector<T>, not aList<T>, since binary search needs indexed access andListhas none. - The function is generic over
T: Comparableand branches onComparable.comparereturningOrdering, so all three outcomes are one exhaustivecase. - A missing value is
Err("value not in array"), the canonical message.Maybe<Int>would have been as natural for “not found”. - Recursion over a half-open range
low..high; each recursive call is in tail position. - The middle element is read with
Vector.get(items, middle)!, which returns the element and traps on an index outside the vector.middleis inlow..highby construction, so there is no miss to handle. - Two
subteststables: found values, and missing values, which assert a different shape.