// Binary search
module binsearch

// Binary search on the interval of integers between `ok` and `ng`.
// If `ng` < `ok`, the result is the smallest integer satisfying `p`.
// Otherwise, the result is the largest integer satisfying `p`.
// `p` must be monotone such that `p(ok)` = `True` and `p(ng)` = `False`.
pub fun binsearchck/binsearch/binsearch: forall<e> (ok : int, ng : int, p : (int) -> <div|e> bool) -> <div|e> int(okok: int: intstd/core/types/int: V, ngng: int: intstd/core/types/int: V, pp: (int) -> $18 bool: intstd/core/types/int: V -> ee: E boolstd/core/types/bool: V): ee: E intstd/core/types/int: V
    if absstd/core/abs: (i : int) -> int(okok: int -std/core/(-).4: (x : int, y : int) -> int ngng: int) <=std/core/(<=).1: (x : int, y : int) -> bool 1 then returnreturn: int okok: int
    val mm: int = (okok: int +std/core/(+).4: (x : int, y : int) -> int ngng: int) /std/core/(/): (x : int, y : int) -> int 2
    if pp: (int) -> $18 bool(mm: int) then binsearchck/binsearch/binsearch: forall<e> (ok : int, ng : int, p : (int) -> e bool) -> e int(mm: int, ngng: int, pp: (int) -> $18 bool)
    else binsearchck/binsearch/binsearch: forall<e> (ok : int, ng : int, p : (int) -> e bool) -> e int(okok: int, mm: int, pp: (int) -> $18 bool)

// Binary search on the interval of float64 between `ok` and `ng`.
// This function returns a number close to the boundary of `p`, which divides
// a set of numbers into two intervals, all numbers in an interval satisfy `p`,
// and all numbers in another one do not.
// `p` must be monotone such that `p(ok)` = `True` and `p(ng)` = `False`.
pub fun binsearch-f64ck/binsearch/binsearch-f64: forall<e> (ok : float64, ng : float64, t : int, p : (float64) -> <div|e> bool) -> <div|e> float64(okok: float64: float64std/core/types/float64: V, ngng: float64: float64std/core/types/float64: V, tt: int: intstd/core/types/int: V, pp: (float64) -> $135 bool: float64std/core/types/float64: V -> ee: E boolstd/core/types/bool: V): ee: E float64std/core/types/float64: V
    if tt: int <=std/core/(<=).1: (x : int, y : int) -> bool 0 then returnreturn: float64 okok: float64
    val mm: float64 = (okok: float64 +std/core/(+).2: (float64, float64) -> float64 ngng: float64) *std/core/(*).1: (float64, float64) -> float64 0.5
    if pp: (float64) -> $135 bool(mm: float64) then
        binsearch-f64ck/binsearch/binsearch-f64: forall<e> (ok : float64, ng : float64, t : int, p : (float64) -> e bool) -> e float64(mm: float64, ngng: float64, tt: int -std/core/(-).4: (x : int, y : int) -> int 1, pp: (float64) -> $135 bool)
    else
        binsearch-f64ck/binsearch/binsearch-f64: forall<e> (ok : float64, ng : float64, t : int, p : (float64) -> e bool) -> e float64(okok: float64, mm: float64, tt: int -std/core/(-).4: (x : int, y : int) -> int 1, pp: (float64) -> $135 bool)