二分探索にぶんたんさく

1導入どうにゅう

この講義こうぎでは、昇順しょうじゅんに整列せいれつされた配列はいれつに対たいする二分探索にぶんたんさくを、探索区間たんさくくかんの不変条件ふへんじょうけんから説明せつめいする。線形探索せんけいたんさくは各要素かくようそを順次比較じゅんじひかくするが、二分探索にぶんたんさくは整列順序せいれつじゅんじょを利用りようして、一回いっかいの比較ひかくで候補区間こうほくかんの一方いっぽうを除外じょがいする。

2問題設定もんだいせってい

$$n\ge 0$$n\geq 0 要素ようその配列はいれつ $$A=(A_0,A_1,\dots ,A_{n-1})$$A=(A_0,A_1,\ldots,A_{n-1}) が

を満みたす、すなわち昇順しょうじゅんに整列せいれつされているとする。目標値もくひょうち $$x$$x に対たいして、$$A_i=x$$A_i=x を満みたす添字そえじ $$i$$i が存在そんざいすればその一ひとつを返かえし、存在そんざいしなければ不在ふざいを返かえす。

重複要素ちょうふくようそを許容きょようするため、$$x$$x が複数ふくすうの位置いちに存在そんざいする場合ばあい、この算法さんぽうはそのうちいずれか一ひとつの添字そえじを返かえす。最初さいしょまたは最後さいごの出現位置しゅつげんいちを求もとめる仕様しようではない。

3半開区間はんかいくかんと中央ちゅうおう

候補こうほとなる添字そえじを半開区間はんかいくかん $$[l,r)$$[l,r) で表あらわす。この区間くかんは $$l$$l を含ふくみ、$$r$$r を含ふくまず、区間長くかんちょうは $$r-l$$r-l である。$$l<r$$l<r のとき、中央添字ちゅうおうそえじを

とする。このとき $$l\le m<r$$l\leq m<r が成立せいりつするため、$$A_m$$A_m は現在げんざいの候補区間内こうほくかんないに存在そんざいする。

4不変条件ふへんじょうけん

反復はんぷくの開始時点かいしじてんで、次つぎの条件じょうけんを維持いじする。

$$x$$x が配列はいれつに存在そんざいするなら、$$A_i=x$$A_i=x を満みたす添字そえじが $$[l,r)$$[l,r) に存在そんざいする。

4.1初期化しょきか

初期値しょきちを $$l=0$$l=0、$$r=n$$r=n とする。候補区間こうほくかん $$[0,n)$$[0,n) は配列全体はいれつぜんたいを含ふくむため、不変条件ふへんじょうけんが成立せいりつする。

4.2保存ほぞん

$$l<r$$l<r のもとで中央ちゅうおう $$m$$m を計算けいさんし、$$A_m$$A_m と $$x$$x を比較ひかくする。

• $$A_m=x$$A_m=x なら、$$m$$m を返かえして終了しゅうりょうする。
• $$x<A_m$$x<A_m なら、昇順性しょうじゅんせいにより、すべての $$i\in [m,r)$$i\in[m,r) について $$A_i\ge A_m>x$$A_i\geq A_m>x である。したがって $$[m,r)$$[m,r) に一致位置いっちいちはなく、$$r=m$$r=m と更新こうしんできる。
• $$A_m<x$$A_m<x なら、昇順性しょうじゅんせいにより、すべての $$i\in [l,m+1)$$i\in[l,m+1) について $$A_i\le A_m<x$$A_i\leq A_m<x である。したがって $$[l,m+1)$$[l,m+1) に一致位置いっちいちはなく、$$l=m+1$$l=m+1 と更新こうしんできる。

いずれの更新こうしんでも、一致位置いっちいちとなり得うる添字そえじだけが新あらたな候補区間こうほくかんに残のこるため、不変条件ふへんじょうけんは保存ほぞんされる。

4.3終了しゅうりょう

$$l=r$$l=r では候補区間こうほくかんが空くうである。不変条件ふへんじょうけんにより、$$x$$x が存在そんざいするなら一致位置いっちいちがこの空区間くうくかんに存在そんざいするはずであり、これは不可能ふかのうである。したがって $$x$$x は配列はいれつに存在そんざいせず、不在ふざいを返かえしてよい。

5停止性ていしせい

更新前こうしんまえの区間長くかんちょうを $$L=r-l>0$$L=r-l>0 とする。$$r=m$$r=m の場合ばあいの新あらたな長ながさは $$m-l$$m-l、$$l=m+1$$l=m+1 の場合ばあいは $$r-m-1$$r-m-1 である。$$l\le m<r$$l\leq m<r から、いずれも $$0\le L^{\prime }<L$$0\leq L'<L を満みたす。

したがって、非負整数ひふせいすうである区間長くかんちょうは一致いっちによって終了しゅうりょうしない各反復かくはんぷくで厳密げんみつに減少げんしょうする。このため反復はんぷくは有限回ゆうげんかいで終了しゅうりょうする。

6計算量けいさんりょう

一回いっかいの更新後こうしんごの区間長くかんちょう $$L^{\prime }$$L' は

を満みたす。$$n=0$$n=0 なら反復はんぷくは行おこなわれない。$$n\ge 1$$n\geq1 では、$$k$$k 回かいの更新後こうしんごに区間長くかんちょうが高々たかだか $$\lfloor n/2^k\rfloor$$\lfloor n/2^k\rfloor となる。$$2^k>n$$2^k>n を満みたせば区間くかんは空くうになるため、反復回数はんぷくかいすうは高々たかだか $$\lfloor {\log }_{2}n\rfloor +1$$\lfloor\log_2 n\rfloor+1 回かいである。よって時間計算量じかんけいさんりょうは $$O\left(\log \right(n+1\left)\right)$$O(\log(n+1))、追加領域ついかりょういきは $$O\left(1\right)$$O(1) である。

7算法さんぽうの要約ようやく

1. $$[l,r)=[0,n)$$[l,r)=[0,n) とする。
2. $$l<r$$l<r の間あいだ、$$m=\lfloor (l+r)/2\rfloor$$m=\lfloor(l+r)/2\rfloor を計算けいさんする。
3. $$A_m=x$$A_m=x なら $$m$$m を返かえす。$$x<A_m$$x<A_m なら $$r=m$$r=m、$$A_m<x$$A_m<x なら $$l=m+1$$l=m+1 とする。
4. $$l=r$$l=r なら不在ふざいを返かえす。

二分探索にぶんたんさくの正当性せいとうせいは、昇順性しょうじゅんせいによる候補こうほの除外じょがい、不変条件ふへんじょうけんの保存ほぞん、および区間長くかんちょうの厳密減少げんみつげんしょうから導みちびかれる。