何となく意識してる次の戦場…
二分技探索(binary search tree)が有効な条件は以下。
- Yes / No で答えられる質問である．
- あるところを境界として，そこより小さいところではずっと Yes だし，そこより大きいところではずっと No である．
- または，あるところを境界として，そこより小さいところではずっと No だし，そこより大きいところではずっと Yes である。
少し一般化するとこんな感じ。
- 要素数Nの広義単調増加な数列A={A0,A1,⋯,AN−1} がある．
- K≦A[i]を満たす要素のうち，最小のもののiをだいたいlog2N回の質問で求める．
広義単調増加な数列というのは，数が小さくなることがない数列のことです。例えば，A={1,3,5,7,9}, K=7の場合、A4=7つまり i=4が答えになります．
おそらく早ければ夏前にこの辺りの課題に取り組んでる筈？
