『数学ガール・乱択アルゴリズム』第2章p43、「見つかった場合」と「見つからなかった場合」を統合する議論において、見つからなかった場合のMをnとするのは唯一の方法ではないことに注意。ここでは他の考え方を試してみる。
「見つかったときのνの位置」として定義したMは、「returnする時点でのkの値」でもある。そう言い換えた上で、見つからなかった場合にも拡張すると、その値はn＋1になる。
以下、紛らわしいのでMの代わりにKを使う。
Kを用いると、ステップ数は順に
1,1,K,K-(1-S),S,0,K-1,K-1,1-S,1で、合計4K+S+1。
いっぽう、番兵つきリニアサーチは
1,1,1,K,K-1,K-1,1,S,0,1-S,1で、合計3K+4。
差をとるとK+S-3であり、これが正ならば番兵つきリニアサーチのほうが早く終わる。
Sで場合分けすると「S=1かつK>2」または「S=0かつK>3」となる。
すなわち、3番目以降で（真に）見つかるか、4番目以降の番兵にぶつかるか、のいずれかである。
テキストではM>2という単純な結果を得ているが、見つかったかどうかによってMの定義が変わるので、M>2の意味合いも変わる。
厳密には「3番目以降で見つかる場合と、3個以上から探して見つからない場合」と言うのが正しい。たまたまSが相殺されたので解釈が容易だが、残っていれば結構厄介になったかもしれない。
番兵つきリニアサーチでは、後者の場合、4番目以降の番兵にぶつかるので、先ほどの結果と一致している。
