二分探索久しぶりに実装した話を書いたが、
こんなの意味あるの？と自分でも思いつつ、まあ趣味だから別に問題なかろう、と半ば無我の境地だったが、調べていく上でめぐる式二分探索に出会えたのはよかった。
例えば、
1 1 2 2 2 3 4 5 5 5
みたいな配列の一番左の2、あるいは一番右の5みたいなものを二分探索したいと思った時に、どういう実装がベターなのだろう？と少し頭を悩ませていた。
pythonならbisect_left, bisect_rightとかを使ってさくっと終わらせてもいいのだが、勉強のためにも自分でベターに実装したいと思っていたら辿り着いたのがめぐる式二分探索。
私がしたかったことは、適切な挿入位置を求めるということだったのだが、なるほど、この、OKかNGかの境目を見つける、ということでも確かにO(log N)ですませられる。
こういう武器を得られるというのは嬉しいことだ。
