二分探索にぶんたんさく

date2026-07-14document_iddoc_0eab994965f14f286340001af35899a7description昇順に整列された配列に対する二分探索を、半開区間の不変条件、停止性、計算量から厳密に説明する。type講義statusactive

algorithmsearchlecture

data/lecture/information/algorithm/search/linear-search.lecture.n.md

1導入どうにゅう

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

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

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

A_{0} \leq A_{1} \leq \dots \leq A_{n - 1}

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

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

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

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

m = ⌊ \frac{l + r}{2} ⌋

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

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

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

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

4.1初期化しょきか

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

4.2保存ほぞん

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

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

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

4.3終了しゅうりょう

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

5停止性ていしせい

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

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

6計算量けいさんりょう

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

L^{'} \leq ⌊ \frac{L}{2} ⌋

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

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

$[l, r) = [0, n)$ とする。
$l < r$ の間あいだ、 $m = ⌊ (l + r) / 2 ⌋$ を計算けいさんする。
$A_{m} = x$ なら $m$ を返かえす。 $x < A_{m}$ なら $r = m$ 、 $A_{m} < x$ なら $l = m + 1$ とする。
$l = r$ なら不在ふざいを返かえす。

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

Binary Search

data/lecture/information/algorithm/search/linear-search.lecture.n.md

1Introduction

This lecture explains binary search on an array sorted in nondecreasing order by means of a search-interval invariant. Linear search compares elements in sequence. Binary search instead uses the sorted order to exclude one part of the candidate interval with each comparison.

2Problem specification

Let $A = (A_{0}, A_{1}, \dots, A_{n - 1})$ be an array of $n \geq 0$ elements satisfying

A_{0} \leq A_{1} \leq \dots \leq A_{n - 1} .

Thus, the array is sorted in nondecreasing order. Given a target $x$ , the algorithm returns an index $i$ satisfying $A_{i} = x$ if such an index exists, and otherwise reports absence.

Duplicate elements are allowed. If $x$ occurs at multiple indices, this algorithm may return any one of them; it does not promise the first or last occurrence.

3Half-open interval and midpoint

Represent the candidate indices by the half-open interval $[l, r)$ . It contains $l$ but not $r$ , and its length is $r - l$ . When $l < r$ , define

m = ⌊ \frac{l + r}{2} ⌋ .

Then $l \leq m < r$ , so $A_{m}$ lies in the current candidate interval.

4Invariant

At the start of every iteration, maintain the following condition:

If $x$ occurs in the array, an index $i$ satisfying $A_{i} = x$ occurs in $[l, r)$ .

4.1Initialization

Set $l = 0$ and $r = n$ . The candidate interval $[0, n)$ contains the entire array, so the invariant holds.

4.2Preservation

Under $l < r$ , compute the midpoint $m$ and compare $A_{m}$ with $x$ .

If $A_{m} = x$ , return $m$ and terminate.
If $x < A_{m}$ , sortedness gives $A_{i} \geq A_{m} > x$ for every $i \in [m, r)$ . Hence no matching index lies in $[m, r)$ , and the update $r = m$ is valid.
If $A_{m} < x$ , sortedness gives $A_{i} \leq A_{m} < x$ for every $i \in [l, m + 1)$ . Hence no matching index lies in $[l, m + 1)$ , and the update $l = m + 1$ is valid.

In either update, every index that can still match remains in the new candidate interval. The invariant is therefore preserved.

4.3Termination condition

When $l = r$ , the candidate interval is empty. If $x$ occurred in the array, the invariant would require a matching index in this empty interval, which is impossible. Thus $x$ is absent, and the algorithm may report absence.

5Termination

Let $L = r - l > 0$ be the interval length before an update. After $r = m$ , the new length is $m - l$ ; after $l = m + 1$ , it is $r - m - 1$ . Since $l \leq m < r$ , both cases satisfy $0 \leq L^{'} < L$ .

Consequently, the nonnegative integer interval length decreases strictly at every iteration that does not terminate with a match. The algorithm must therefore terminate after finitely many iterations.

6Complexity

After one update, the new interval length satisfies

L^{'} \leq ⌊ \frac{L}{2} ⌋ .

If $n = 0$ , the loop performs no iterations. If $n \geq 1$ , then after $k$ updates its length is at most $⌊ n / 2^{k} ⌋$ . Once $2^{k} > n$ , the interval is empty, so the algorithm performs at most $⌊ \log_{2} n ⌋ + 1$ iterations. Its time complexity is $O (\log (n + 1))$ , and its auxiliary-space complexity is $O (1)$ .

7Algorithm summary

Set $[l, r) = [0, n)$ .
While $l < r$ , compute $m = ⌊ (l + r) / 2 ⌋$ .
If $A_{m} = x$ , return $m$ . If $x < A_{m}$ , set $r = m$ ; if $A_{m} < x$ , set $l = m + 1$ .
If $l = r$ , report absence.

The correctness of binary search follows from candidate exclusion justified by sortedness, preservation of the invariant, and strict decrease of the interval length.