二分探索 (再帰版)
同じ二分探索を、今度は再帰で書きます。半分を捨てる考え方は前回のままです。変わるのは「今どこを見ているか」を何で持ち回るか、という一点だけです。
切った配列の 0 番目は、元の 0 番目ではない
再帰で書くとき、まず思いつくのは「右半分の配列を作って、それを自分自身に渡す」書き方です。ところが、これをやると答えの位置がずれます。
Python
arr = [1, 3, 5, 7, 9, 11]
right = arr[3:] # [7, 9, 11]
right.index(9) # 1
arr.index(9) # 4切り出した配列の中では 9 は 1 番目ですが、元の配列では 4 番目です。返したいのは元の配列での位置なので、切るたびに「元の配列で何番ずれたか」を自分で足し戻さなければいけません。
ここを忘れると、値そのものは見つかるのに位置だけが違う、という気づきにくい壊れ方をします。テストの期待値と 3 や 4 だけずれていたら、まずこれを疑ってください。
配列は切らずに、見る範囲だけを渡す
ずれを足し戻す代わりに、配列を切らないという手があります。配列はそのまま置いておき、「今は何番目から何番目までを見ている」という 2 つの数値だけを引数で持ち回ります。
位置が最初から最後まで元の配列基準なので、足し戻しが要りません。おまけに配列のコピーも作らないので、要素が増えても速度が落ちません。切って渡す書き方は、1 段降りるたびに配列を丸ごと作り直しています。
外から呼ばれる関数は配列と目当ての値の 2 つしか受け取らないので、範囲を受け取る関数は内側にもう 1 つ用意することになります。外側は最初の範囲を渡して呼ぶだけ、内側が実際に半分を捨てながら降りていく、という役割分担です。
Java や Go では配列の切り出し自体が手間なので、最初からこの形で書くのが普通です。Python や JavaScript は切り出しが手軽に書けてしまうぶん、うっかり切って渡す書き方に流れやすいので気をつけてください。
範囲がすれ違ったら止まる
再帰である以上、止まる条件が要ります。範囲を表す 2 つの数値は、半分を捨てるたびに近づいていきます。1 つの要素まで縮み、それも違えば、開始位置が終了位置を追い越します。
追い越した状態は「見るべき要素が 1 つも残っていない」という意味です。そこが基底ケースになります。
範囲の広さが毎回半分になるので、100 万件でも 20 段ほどしか降りません。1 要素ずつ縮む再帰なら 100 万段ですが、半分ずつ縮むので浅いところで止まります。降りすぎて積み上がる心配はまずしなくて構いません。
ここでも、進むときに真ん中を次の範囲に残さないことが大事です。真ん中は既に見て違うと分かっているので、次の範囲からは外します。残したままにすると範囲が縮まらず、同じ場所を延々と見続けることになります。
再帰で書くか繰り返しで書くかは、速さの問題ではなく読みやすさの問題です。範囲を 2 つの数値で持ち回る形にしておけば、どちらへ書き換えるのも簡単になります。
要件
- 再帰関数で実装する
- 計算量は O(log n)
- 配列のスライスではなく index 範囲を引数で渡す
入出力例
binarySearchRec([1,3,5,7,9,11], 11) → 5
binarySearchRec([2,4,6,8], 2) → 0
binarySearchRec([1,2,3,4,5], 3) → 2
binarySearchRec([1,3,5,7], 4) → -1
binarySearchRec([42], 42) → 0ヒント
