2分探索したいけれど上限が見積もれないとき

2分探索は答えを確実に含むような十分広い区間から初めて、区間を半分にしていくことにより、対数時間で答えの存在範囲を絞り込む方法である。整数値であれば、区間が1になるまで続けることで誤差なしで求めることもできる。しかし、このままでは初期区間がわからないとき使えない。どうすればよいか。

前半に初期区間を求めるステップを加える。十分狭い区間から初めて、倍々にしていけばよい。こうすれば対数時間という特性を保ったまま求めることできる。

ついでに、計算量も出力依存にすることができる。

例えば、所望の要素が前の方に来やすい配列上で2分探索で要素を探索するとき、配列の長さに依存するする計算量では少々残念なことになるが、この方法であれば所望の要素の位置に依存する計算量にできるので数倍程度速くできる。(log 同士なので本当に定数倍の差みたいなものだが)