[ruby-list:49317] Re: Array#bsearchで求められる前提について
From:
Yusuke Endoh <mame@...>
Date:
2013-04-10 11:20:11 UTC
List:
ruby-list #49317
遠藤といいます。
2013年4月10日 17:23 Kouhei Yanagita <yanagi@shakenbu.org>:
> 2.0.0p0で
>
> (1..10).to_a.bsearch { |e| e < 3 }
>
> がnilになるのですが、これは「配列がソートされていない」ということでいいのでしょうか。
はい、そうなります。rdoc では "monotone (or sorted)" と表現しています。
> 言い換えると、Array#bsearchで前提とされているソートとは、
> 「ブロックを満たす任意の要素は、ブロックを満たさない任意の要素より後ろにある」という意味であって、
> 「ブロックを満たす任意の要素は、ブロックを満たさない任意の要素より前にある」状態は含まない
> ということでいいのでしょうか。
その通りです。
厳密に言うと、あるインデックス i (0 <= i <= ary.size) に対して、
- i より小さいインデックスの要素に対してブロックは false を返し、かつ
- i と等しいか大きいインデックスの要素に対してブロックは true を返す
という条件を満たさないとダメです (この時 ary[i] を返す) 。
詳しくは rdoc を見てください。
http://ruby-doc.org/core-2.0/Array.html#method-i-bsearch
2013年4月10日 17:23 Kouhei Yanagita <yanagi@shakenbu.org>:
> こんにちは。柳田と申します。
>
> 2.0.0p0で
>
> (1..10).to_a.bsearch { |e| e < 3 }
>
> がnilになるのですが、これは「配列がソートされていない」ということでいいのでしょうか。
>
> 言い換えると、Array#bsearchで前提とされているソートとは、
> 「ブロックを満たす任意の要素は、ブロックを満たさない任意の要素より後ろにある」という意味であって、
> 「ブロックを満たす任意の要素は、ブロックを満たさない任意の要素より前にある」状態は含まない
> ということでいいのでしょうか。
>
> ソースコードを読むとその前提で実装されているように見えるのですが、
> 仕様として意図されたものなのかどうかわからなかったので質問します。
>
>
> --
> 柳田 浩平 / やなぎた こうへい
> Kouhei Yanagita <yanagi at shakenbu.org>
>
--
Yusuke Endoh <mame@tsg.ne.jp>