From: matz@... (Yukihiro Matsumoto)
Date: 2002-05-18T02:18:56+09:00
Subject: [ruby-dev:17132] Re: Array#bsearch

まつもと ゆきひろです

In message "[ruby-dev:17131] Re: Array#bsearch"
    on 02/05/18, Beyond <beyond@big.or.jp> writes:

|assoc が、associated-array（または、array of arrays）を仮定しているよう
|に、bsearch が sorted-array を仮定していても良いと思うんですが...。

いや、assocはarray of arraysでないものに適用された場合にはそ
の挙動は「みつからない(データが存在しないから)」ということで
簡単に定義できますが、bsearch(3)がsortしてないarrayに適用さ
れた場合の挙動はassocに比べてもうちょっと不確実な気がします。
つまり、部分的にソートされた配列とかを考えると「みつかるかも
しれないし、みつからないかもしれない」ということになるのでは
ないかと。範囲が与えられているので落ちてしまうことはあんまり
ないとは思いますが。

しかし、範囲が与えられていても、比較関数が妙な値を返すと落ち
てしまうqsortの実装を知っているので(Rubyがqsortの実装を自分
でもっている理由のひとつ)、まだ安心はできないんですが。

|bsearch は、qsort と同じく、ANSI C/C++の標準関数です（stdlib.h）。
|bsearch の方が実装が簡単なので、qsort があって bsearch が無いと言うのは
|余程、珍しい処理系だと思います。

実装が簡単だから存在しないことが珍しいかどうか私にはよくわか
りませんが(むしろ逆のような)、bsearchはPOSIXには定義されてい
ませんね(qsortはある)。それにC99以前のANSI Cでも定義されてま
したっけ。

あと、上記の理由があるのでbsearchを仮に採用するとしても、結
局自前で実装することになると思います。

                                まつもと ゆきひろ /:|)