与えられた要素が配列に保存されているか検査するために、 しばしば順序付けられた配列に対して二分探索を行なうことがあります。 また整数に対して増加や減少する関数の逆関数を作るのに使うこともできます。 次のコードで定義している関数 bsearch_fun は、 i が lb から i0 までの範囲では f(i) <= x0 を維持し、 i が i0+1 から ub までの範囲では x0 < f(i) を維持するような整数 i0 を返します:
// // The type [uint] is for unsigned integers // fun bsearch_fun ( f: int -<cloref1> uint , x0: uint, lb: int, ub: int ) : int = if lb <= ub then let val mid = lb + (ub - lb) / 2 in if x0 < f (mid) then bsearch_fun (f, x0, lb, mid-1) else bsearch_fun (f, x0, mid+1, ub) // end of [if] end else ub // end of [if] // end of [bsearch_fun]
// // Assuming that [uint] is of 32 bits // val ISQRT_MAX = (1 << 16) - 1 // = 65535 fun isqrt (x: uint): int = bsearch_fun (lam i => square ((g0i2u)i), x, 0, ISQRT_MAX) // end of [isqrt]
この章で紹介したコード全体と追加のテストコードは オンライン から入手できます。 (訳注: このコードを atscc でコンパイルする際には -DATS_MEMALLOC_LIBC オプションが必要です。)