bsearch が 2 つの値を持つ配列の最初の要素と一致する場合、nil を返します。なぜ？

概要

配列に2つの値があるときに、bsearchメソッドがnilを返す理由がわかりません。

arr = [1, 2]

arr.bsearch { |el| el < 2 }

解決策

ドキュメントを検索する

Array#bsearch のドキュメントを注意深く読む必要があります。 bsearch には 2 つの形式またはモードがあると述べられています。「最小値検索モードと任意の検索モード。どちらの場合も、配列の要素はブロックに関して単調 (またはソート) でなければなりません。」 find-minimum モードでは、ブロックは true または false を返します。 find-any モードでは、配列の要素と同じクラスの値がブロックによって返されます。したがって、find-minimum モードを使用していることになります。

また、ドキュメントから、find-minimum モードでは、次のようにインデックス i, 0 <= i <= ary.size が存在する必要があります。

このメソッドは i 番目の要素を返します。 i が ary.size に等しい場合、nil を返します。」

コードを調べる

次に、少し変更したステートメントを調べてみましょう。

arr = [1, 2, 3]
arr.bsearch { |el| el < 2 } #=> nil

bsearch の使用によって課せられる要件を満たすインデックス 0、1、または 2 を見つけたいと考えています。

対象のインデックスが 0 であるとします。ゼロより小さいインデックスはないため、arr[1] < 2 と arr[2] < 2 (2 < 2 および 3 < 2) が両方とも真かどうかをテストします。実際にはどちらも誤りです。したがって、インデックス 0 は考慮から除外されます。

ここで、ドキュメントで参照されているインデックスが 1 だったとします。arr[0] < 2 が false であることが必要ですが、これは true です。したがって、インデックス 1 を除外できます。

インデックスが 2 に等しくなるには、arr[0] < 2 と arr[1] < 2 の両方が false である必要がありますが、実際には両方とも true です。

besearchを使用するための要件を満たすインデックスが存在しないため、nilが返されます。

コードを修正する

arr = [1, 2, 3] の場合、式は次のように記述する必要があることは明らかです。

arr.bsearch { |el| el >= 2 }      #=> 2
arr.bsearch { |el| el > 2  }      #=> 3
arr.bsearch { |el| el > 0  }      #=> 1
arr.bsearch { |el| el > 3  }      #=> nil

その他の例

配列に整数が含まれる例をさらにいくつか示します。

ary = [2, 4, 6]

ary.bsearch { |el| el > -99 }     #=> 2
ary.bsearch { |el| el > 1 }       #=> 2
ary.bsearch { |el| el > 2 }       #=> 4
ary.bsearch { |el| el >= 2 }      #=> 2
ary.bsearch { |el| el >= 6 }      #=> 6
ary.bsearch { |el| el > 6 }       #=> nil

配列は増加しないこともできます

配列は非減少である必要はなく、単調である必要があることに注意してください。これは、非減少または非増加を意味します。以下は、配列が増加していない (実際には厳密に減少している) 例です。もちろん、ブロック計算もそれに応じて調整する必要があります。

ary = [6, 4, 2]

ary.bsearch { |el| el <= 7 }    #=> 6
ary.bsearch { |el| el <= 99}    #=> 6
ary.bsearch { |el| el < 5 }     #=> 4
ary.bsearch { |el| el <= 4 }    #=> 4
ary.bsearch { |el| el < 4 }     #=> 2
ary.bsearch { |el| el <= 2 }    #=> 2
ary.bsearch { |el| el < 2 }     #=> nil  
ary.bsearch { |el| el <= 1 }    #=> nil

配列には数値以外の値が含まれる場合があります

唯一の要件は、要素のペアが宇宙船演算子 <=> と比較できることです。 a <=> b は、a < b の場合は -1 を返し、a == b の場合は 0 を返し、a > b の場合は 1 を返します。

たとえば、文字列の場合、bsearch では String#<=> が使用されます。ここではいくつかの例を示します。

ary = ['brush', 'keep', 'task']

ary.bsearch { |s| s >= 'hi' }     #=> "keep"
ary.bsearch { |s| s >= 'align' }  #=> "brush"
ary.bsearch { |s| s >= 'mama' }   #=> "task"
ary.bsearch { |s| s >= 'tar' }    #=> "task"
ary.bsearch { |s| s >= 'tax' }    #=> "nil"