instance method Array#bsearch

ブロックの評価結果で範囲内の各要素の判定を行い、条件を満たす値を二分探索(計算量は O(log n))で検索します。要素が見つからない場合は nil を返します。self はあらかじめソートしておく必要があります。

本メソッドはブロックを評価した結果により以下のいずれかのモードで動作します。

• find-minimum モード
• find-any モード

find-minimum モード(特に理由がない限りはこのモードを使う方がいいでしょう)では、条件判定の結果を以下のようにする必要があります。

• 求める値がブロックパラメータの値か前の要素の場合: true を返す
• 求める値がブロックパラメータより後の要素の場合: false を返す

ブロックの評価結果が true になる最初の要素を返すか、nil を返します。

例

ary = [0, 4, 7, 10, 12]
ary.bsearch {|x| x >=   4 } # => 4
ary.bsearch {|x| x >=   6 } # => 7
ary.bsearch {|x| x >=  -1 } # => 0
ary.bsearch {|x| x >= 100 } # => nil

find-any モードは bsearch(3) のように動作します。ブロックは真偽値ではなく、以下のような数値を返す必要があります。求める要素が配列の i 番目から j-1 番目までに入っているとします。またブロックパラメータの値のインデックスを k とします。

• ブロックパラメータの値が求める値の範囲よりも小さい（0 <= k < i）場合: 正の数を返す
• ブロックパラメータの値が求める値の範囲に合致する（i <= k < j）場合: 0 を返す
• ブロックパラメータの値が求める値の範囲よりも大きい（j <= k < self.size）場合: 負の数を返す

ブロックの評価結果が 0 になるいずれかの要素を返すか、nil を返します。

例

ary = [0, 4, 7, 10, 12]
# 4 <= v < 8 になる要素を検索
ary.bsearch {|x| 1 - x / 4 } # => 4 or 7
# 8 <= v < 10 になる要素を検索
ary.bsearch {|x| 4 - x / 2 } # => nil

上記の 2 つのモードを混在して使用しないでください(ブロックの評価結果は常に true/false、数値のいずれかを一貫して返すようにしてください)。また、二分探索の各イテレーションで値がどのような順序で選ばれるかは未規定です。

ブロックが与えられなかった場合は、 Enumerator のインスタンスを返します。

[EXCEPTION] TypeError:

ブロックの評価結果が true、false、nil、数値以外であった場合に発生します。

[SEE_ALSO] Array#bsearch_index, Range#bsearch, https://magazine.rubyist.net/articles/0041/0041-200Special-note.html