binarysearchでは、要素が見つからない場合、なぜそれを行うべきであるかを引く規則はなぜですか？

Question

私はこれがぎこちなくなっていることを知っていますが、バイナリ検索を実行しても要素が見つからない場合、返される合理性は何ですか。(-(insertion point) -1)特に-1部分。これはJavaがそれを行う方法であり、なぜ彼らが-(insertion point)の代わりに-1という規約を作ったのかわかりません。明らかに、負の値は、配列/リストに実際に値が見つからなかったことを示します。私はそれがCから来ていると推測しています。ここでは、ビット単位の演算をネゲートして引いた方が簡単です。

注：このコンベンションを使用するC、C++、Javaで書かれたコードを見てきましたが、どこから来ているのでしょうか？

Answer 1

これは、挿入ポイントがゼロであり、int（浮動小数点数とは異なります）に-0を持たないためです。したがって、明確に示すために他の方法が必要です。

それはJavadocに言うように：これは、キーが見つかった場合にだけ戻り値が> = 0になることが保証さ

注意。

もちろん、挿入位置を表す他の方法もあります。要素を適切に挿入するためにコンテナのサイズなどの余分な情報を必要としないため、これはちょうど非常にエレガントです。

---

慣習がどこで発生したかという点では、時間の霧、私は賭けます！

純粋な推測として、私はそれがC言語（あるいはもっと早い言語でも）で起こっていると想像することができます。ここでは、選択肢よりも値をエンコードする方がはるかにクリーンな方法でした。

「明白な」代替符号化は挿入位置を示すために存在/不在を示すために符号ビットを使用し、残りのビットであるかもしれない：

S PPPP....P 
^   0 means "present", 1 means "absent" 
    ^---....^ These bits denote the position in the container. 

サインした場合の位置を抽出しますビットが設定されている場合は、ビットをマスクする必要があります。これはJavaで簡単です。intは32ビットで定義されています（単純にvalue & 0x7FFFFFFを使用します）。 -

value = binarySearch(...); 
if (value < 0) { 
    insertionPosition = value & ~(1 << sizeof(int) * 8 - 1); 
    ... 
} 

（JavaプログラマはCを書くことを試みるべきではない理由です...それは非常に適切ではない場合、私を許して）：しかし、ポータブルCでそれを書くために、あなたのような何かをする必要があると思いますでも、固定幅の

は、それは少し不可解です：

あなたは多くの場所でそれを記述する必要があれば、間違って取得するにはかなり醜い、むしろ簡単です

value = binarySearch(...); 
if (value < 0) { 
    insertionPosition = value & 0x7FFFFFFF; // What's this magic number?! 
    ... 
} 

。確かに、あなたはこの数学をするための小さなメソッドを書くことができますが、メソッドコールは高価です（少なくとも、彼らはその日に戻ってきたかもしれません）。

(-(insertion point) -1)規則を使用して、簡単な書くことができ、読みやすい、迅速なコード：

value = binarySearch(...); 
if (value < 0) { 
    insertionPosition = -value - 1; 
    ... 
}