前置き
たかが binary search, されど binary search
バイナリサーチを自分で書いたことがない人がいようか。もしない人がいれば何度も実装してみることをおすすめする。楽しいよ。 while の終了条件をどうするか、left, rightの更新式をどうするか、などは自分で書こうとすると意外と混乱することに気づける。
実際のプロダクト開発で使うことはあまりないだろうが、競技プログラミングやGAFAのコーディング試験では必要とされる能力だ。基礎力を試せるという意味でもある。実際私はGoogleのコーディング試験で実装する場面があり、緊張のせいもあったが手こずってしまった経験がある。
C++の勉強でAtCoderを継続的に解いているのだが、先日他の人の提出をみている*1 時に、binary searchの書き方で なるほどな と感心したのでメモっておく。
本題
月並みに、昇順にソートされた重複のない配列Aからtargetが何番目にあるかを返したいときを考える。
while (left + 1 < right) { // あるいは right - left > 1 など mid = left + (right - left) / 2; if (A[mid] > target) right = mid; else left = mid; } return left;
while の条件式の中身は、left と rightが隣同士になるまでという意味だ。
この書き方の何がいいかというと、left はOK, right は NG, という明確さがあり、全ての要素についてOKかNGを判定したら終わり、という直感的なわかりやすさだ。つたわるだろうか。
OKぎりぎりを返したければleft, ぎりぎりNGを返したければrightをreturn すればいい。 +1 とか -1 とかが出てくるのが一箇所だけで住むのはとてもいい。
今後使っていこうと思う。
補足
- 上のコードで、left は最初の要素（多くの場合０）、right は最後の次の要素（多くの場合len(A)など）で、right は参照されることのない値を初期値に設定する。
- mid を求める際に (left + right) / 2 としないのはオーバーフロー対策。 （ちょっと玄人感に浸れる）
余談
ちなみに、これまではどうやって書いていたかといえば、
while (left < right) {
mid = left + (right - left) / 2;
if (A[mid] > target) right = mid;
else left = mid + 1;
}
return left - 1;
と書いていた。どこかで目にした書き方で、そのまま使っていたのだが、実を言えば毎回不安になって終了判定やきわどい条件を頭の中で検証していた。
今回見つけた方法のほうが、個人的にはわかりやすいと思った。
