二分探索にぶんたんさく

導入どうにゅう

二分探索にぶんたんさくで最重要さいじゅうようなのは、真まん中なかを見みることそのものではなく、1 回かいの比較ひかくで半分はんぶんを捨すてられる条件じょうけんを持もっていることです。

その条件じょうけんが、配列はいれつが整列せいれつしていることです。順序じゅんじょがあるからこそ、中央ちゅうおうの値あたいと比くらべた結果けっかから、左半分ひだりはんぶんか右半分みぎはんぶんのどちらかをまとめて除外じょがいできます。この講義こうぎでは、その論理ろんりを不変条件ふへんじょうけんとして整理せいりします。

用語ようごと定義ていぎ

まず主役しゅやくになる用語ようごをそろえます。

二分探索にぶんたんさくBinary search とは、整列済せいれつずみの配列はいれつで、探索範囲たんさくはんいを半分はんぶんずつ狭せばめながら目標値もくひょうちを探さがす方法ほうほうです。

整列済せいれつずみsorted とは、$$A_0\text{[PARSE ERROR: Undefined("Command("le")")]}{A}_1\text{[PARSE ERROR: Undefined("Command("le")")]}\text{[PARSE ERROR: Undefined("Command("dots")")]}\text{[PARSE ERROR: Undefined("Command("le")")]}{A}_{n-1}$$A_0\le A_1\le \dots \le A_{n-1} が成なり立たつことです。

探索区間たんさくくかんsearch interval は、まだ $$x$$x があるかもしれない範囲はんいです。この講義こうぎでは $$[l,r)$$[l,r) を使つかい、候補こうほは $$A_l,A_{l+1},\text{[PARSE ERROR: Undefined("Command("dots")")]},A_{r-1}$$A_l,A_{l+1},\dots,A_{r-1} とします。

中央ちゅうおうmiddle の添字そえじは $$m=\lfloor \frac{l+r}{2}\rfloor$$m=\left\lfloor\frac{l+r}{2}\right\rfloor とします。

不変条件ふへんじょうけんinvariant とは、反復はんぷくの各段階かくだんかいでずっと保たもたれる条件じょうけんです。

方針ほうしん

二分探索にぶんたんさくでは、まず「もし $$x$$x が存在そんざいするなら、必かならず探索区間たんさくくかん $$[l,r)$$[l,r) の中なかにある」という不変条件ふへんじょうけんを立たてます。

つぎに中央ちゅうおう $$A_m$$A_m と $$x$$x を比くらべます。配列はいれつが整列済せいれつずみなので、

• $$x<A_m$$x<A_m なら $$m$$m 以降いこうは全部ぜんぶ大おおきすぎる
• $$x>A_m$$x>A_m なら $$m$$m 以前いぜんは全部ぜんぶ小ちいさすぎる

と言いえます。つまり、中央ちゅうおうを見みる理由りゆうは「半分はんぶんを捨すてる証拠しょうこを得えるため」です。

導出どうしゅつ

どこまで成なり立たつか

二分探索にぶんたんさくが使つかえるのは、配列はいれつや探索対象たんさくたいしょうに順序じゅんじょがあり、その順序じゅんじょを使つかって「こちら側がわは全部ぜんぶ不可能ふかのう」と言いえるときです。

したがって、整列せいれつしていない配列はいれつにはそのままでは使つかえません。また、比較ひかくの結果けっかから半分はんぶんを捨すてられない問題もんだいにも使つかえません。

つまり、前提条件ぜんていじょうけんは線形探索せんけいたんさくより強つよいですが、その代かわりに計算量けいさんりょうは $$O\left(\log n\right)$$O(\log n) まで下さがります。

見分みわけ方かた

• 比較ひかくの結果けっかだけで、ある範囲はんいをまとめて不可能ふかのうにできるなら、二分探索にぶんたんさくを疑うたがいます。
• 配列はいれつが整列せいれつしている、あるいは「単調たんちょうに真偽しんぎが切きり替かわる」構造こうぞうがあるなら、半分はんぶんを捨すてられる可能性かのうせいがあります。
• 順序じゅんじょはあるが、比較ひかくしてもどちら側がわを全部ぜんぶ捨すててよいか言いえないなら、二分探索にぶんたんさくではなく別べつの方法ほうほうを考かんがえます。

最終形さいしゅうけい

整列済せいれつずみ配列はいれつに対たいして、候補こうほを半開区間はんかいくかん $$[l,r)$$[l,r) で持もちます。

• 初期値しょきちは $$[l,r)=[0,n)$$[l,r)=[0,n) です。
• 中央ちゅうおう $$m=\lfloor \frac{l+r}{2}\rfloor$$m=\left\lfloor\frac{l+r}{2}\right\rfloor を取とります。
• $$A_m=x$$A_m=x なら成功せいこうです。
• $$x<A_m$$x<A_m なら $$r=m$$r=m にします。
• $$x>A_m$$x>A_m なら $$l=m+1$$l=m+1 にします。
• $$l=r$$l=r になったら「存在そんざいしない」と結論けつろんします。

したがって二分探索にぶんたんさくは

であり、計算量けいさんりょうは $$\text{[PARSE ERROR: Undefined("Command("boxed")")]}O\left(\log n\right)$$\boxed{O(\log n)} です。

一言ひとことでいうと

• 中央ちゅうおうを見みるのは、中央ちゅうおうが特別とくべつだからではなく、半分はんぶんを捨すてる根拠こんきょを得えやすいからです。
• 本体ほんたいは、「もし $$x$$x があるなら $$[l,r)$$[l,r) の中なかにある」という不変条件ふへんじょうけんです。
• 整列せいれつという前提条件ぜんていじょうけんを使つかって候補集合こうほしゅうごうを半分はんぶんずつ削けずる、それが二分探索にぶんたんさくです。

関連かんれんリンク