二分探索

モールス信号の二分法検索表を図式で表したものです。上向きのステップは短点（.）、下向きのステップは長点（-）を表します。止まる位置がコードの文字を示します。

T –	月 – –	お – – –	CH – – – –
			Ö – – – ·
		G – – ·	Q – – · –
			Z – – · ·
	N – ·	K – · –	Y – · – –
			C – · – ·
		D – · ·	X – · · –
			B – · · ·
E ·	A · –	W · – –	J · – – –
			P · – – ·
		R · – ·	Ä · – · –
			L · – · ·
	私 ・ ・	U · · –	Ü · ​​· – –
			F · · – ·
		S · · ·	V · · · –
			H · · · ·

コンピュータサイエンスにおいて、二分探索とは、各ステップで2つの異なる選択肢（二分法^{[ 1 ]}、または2つ以上の場合は多分法^{[ 2 ]} ）から選択する探索アルゴリズムである。これは分割統治アルゴリズムの一種である。よく知られた例としては二分探索^{[ 3 ]}がある。

抽象的には、二分探索は暗黙的な二分木構造の辺を辿り、葉（目標または最終状態）に到達するまで探索すると考えることができる。^{[ 4 ]}これにより、可能な状態の数と実行時間の間に理論的なトレードオフが生じる。k回の比較をした場合、アルゴリズムはO(2k)個の可能な状態および/または可能な目標にしか到達でき^ない。

二分探索の中には、ハフマン符号化で使用されるハフマン木や、20の質問で使用される暗黙的分類木のように、木の葉でのみ結果を得るものがあります。また、モールス信号の二分探索表のように、木の内部ノードの少なくとも一部でも結果を得る二分探索もあります。このように、定義には多少の曖昧さがあります。実際にはどのノードからも2つのパスしか存在しない場合もありますが、各ステップには3つの可能性があります。つまり、どちらかのパスを選択するか、そのノードで停止するかです。

二分検索は修理マニュアルでよく使用され、故障木に似たフローチャートでグラフィカルに示されることもあります。

参照

• 二分探索アルゴリズム

参考文献

1. 「二分法検索」 . xlinux.nist.gov . 2024年5月30日閲覧。
2. "polychotomy" . xlinux.nist.gov . 2024年5月30日閲覧。
3. 「Pythonでのバイナリ検索の実装：チュートリアル | Built In」 . builtin.com . 2023年12月7日閲覧。
4. ドナルド・アービン・クヌース（1997年）『コンピュータプログラミングの芸術』（第3版）レディング、マサチューセッツ州：アディソン・ウェスレー。ISBN 978-0-201-89683-1。

外部リンク

• 二分探索（再帰および反復）のための Python プログラム
• 二分探索