Ruby 2.2.0 リファレンスマニュアル > ライブラリ一覧 > 組み込みライブラリ > Rangeクラス > bsearch
bsearch {|obj| ... } -> object | nil
[permalink][rdoc]bsearch -> Enumerator
ブロックの評価結果で範囲内の各要素の大小判定を行い、条件を満たす値を二 分探索(計算量は O(log n))で検索します。要素が見つからない場合は nil を 返します。
本メソッドはブロックを評価した結果により以下のいずれかのモードで動作し ます。
find-minimum モード(特に理由がない限りはこのモードを使う方がいいでしょ う)では、条件判定の結果を以下のようにする必要があります。
ブロックの評価結果が true になる最初の要素を返すか、nil を返します。
例:
ary = [0, 4, 7, 10, 12] (0...ary.size).bsearch {|i| ary[i] >= 4 } # => 1 (0...ary.size).bsearch {|i| ary[i] >= 6 } # => 2 (0...ary.size).bsearch {|i| ary[i] >= 8 } # => 3 (0...ary.size).bsearch {|i| ary[i] >= 100 } # => nil (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } # => 1.0
find-any モードは bsearch(3) のように動作します。ブロックは真偽値 ではなく、以下のような数値を返す必要があります。求める値の範囲がx...y (x <= y)であるとします。また、ブロックパラメータの値を v とします。
ブロックの評価結果が 0 になるいずれかの要素を返すか、nil を返します。
例:
ary = [0, 100, 100, 100, 200] (0..4).bsearch {|i| 100 - ary[i] } # => 1, 2 or 3 (0..4).bsearch {|i| 300 - ary[i] } # => nil (0..4).bsearch {|i| 50 - ary[i] } # => nil
上記の 2 つのモードを混在して使用しないでください(ブロックの評価結果は 常に true/false、数値のいずれかを一貫して返すようにしてください)。 また、二分探索の各イテレーションで値がどのような順序で選ばれるかは 未規定です。
ブロックが与えられなかった場合は、 Enumerator のインスタンスを返します。
[SEE_ALSO] Array#bsearch