BinarySearch

type SearchResult = {#keyFound : Nat; #notFound : Nat}

public func binarySearchNode<K, V>(
  array : [var ?(K, V)],
  compare : (K, K) -> O.Order,
  searchKey : K,
  maxIndex : Nat
) : SearchResult

Searches an array for a specific key, returning the index it occurs at if #keyFound, or the child/insert index it may occur at if #notFound. This is used when determining if a key exists in an internal or leaf node, where a key should be inserted in a leaf node, or which child of an internal node a key could be in.

Note: This function expects a mutable, nullable, array of keys in sorted order, where all nulls appear at the end of the array. This function may trap if a null value appears before any values. It also expects a maxIndex, which is the right-most index (bound) from which to begin the binary search (the left most bound is expected to be 0)

Parameters:

• array - the sorted array that the binary search is performed upon
• compare - the comparator used to perform the search
• searchKey - the key being compared against in the search
• maxIndex - the right-most index (bound) from which to begin the search