二分探索
最終更新
二分探索は、**ソート済み**の配列で探索範囲を繰り返し半分に絞ることで目的の値を見つけます。中央の要素を目的の値と比較し、一致すれば探索は終了。一致しなければ、目的の値を含み得ない半分を捨て、範囲をもう一方の半分に縮めます。1回の比較ごとに残りの要素の半分が除外されるため、実行時間は O(log n) になります — 100万個のソート済みの値を探索しても、比較は最大でも約20回で済みます。
上のアニメーションは lo、mid、hi の各ポインタを表示し、比較のたびに除外された半分を薄く表示します。唯一の絶対条件は、配列があらかじめソート済みであること — 未ソートのデータには線形探索を使うか、先にソートが必要です（マージソートを参照）。同じ「半分に絞る」考え方は二分探索木の基盤でもあります。
時間計算量と空間計算量
| ケース | 計算量 | 備考 |
|---|---|---|
| 最良ケース | O(1) | 最初の比較で中央の要素が目的の値である場合。 |
| 平均ケース | O(log n) | 1回の比較ごとに残りの範囲が半分になる。 |
| 最悪ケース | O(log n) | 一致または不在の確定前に、範囲が1要素まで縮む。 |
| 空間 | O(1) | 反復版は lo、hi、mid のインデックスだけを保持する。 |
ステップごとの説明
| ステップ | 何が起こるか |
|---|---|
| 1 | lo をソート済み配列の最初のインデックスに、hi を最後のインデックスに設定する。 |
| 2 | 中央のインデックスを計算する：mid = (lo + hi) // 2。 |
| 3 | a[mid] が目的の値と等しければ mid を返す — 発見。 |
| 4 | a[mid] が目的の値より**小さい**なら、目的の値は右半分にしかあり得ない：lo = mid + 1 とする。 |
| 5 | a[mid] が目的の値より**大きい**なら、左半分を探索する：hi = mid - 1 とする。 |
| 6 | lo <= hi の間、ステップ2から繰り返す。範囲が空になったら、目的の値は配列に存在しない。 |
具体例
[1, 2, 3, 5, 7, 8, 9] から 5 を探索する場合：
| パス | 範囲 (lo..hi) | mid | a[mid] | 動作 |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5 — インデックス3で目的の値を発見。 |
見つからない場合のステップ
同じ配列で 4 を探索すると、範囲が空になっていく様子がわかります：
| パス | 範囲 (lo..hi) | mid | a[mid] | 動作 |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4 — 左半分を探索、hi = 2。 |
| 2 | 0..2 | 1 | 2 | 2 < 4 — 右半分を探索、lo = 2。 |
| 3 | 2..2 | 2 | 3 | 3 < 4 — lo が3になり範囲が空になる：見つからない。 |
二分探索を使うべき場面
| 使うべきとき | 避けるべきとき |
|---|---|
| データがすでにソート済みのとき（または何度も探索するとき） | データが未ソートで1回しか探索しないとき — 先にソートすると O(n log n) かかる |
| コレクションが高速なランダムアクセスに対応しているとき（配列） | 順次アクセスしかできないとき（連結リスト） |
データセットが大きいとき — O(log n) は大規模で真価を発揮する | データセットがごく小さいとき — 単純な走査でも同じくらい速く、より簡単 |
Binary Searchのコード
Python, JavaScript, Java, C++, C, Pseudocodeによるクリーンで実行可能なBinary Searchの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのBinary Searchのコード
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))JavaScriptでのBinary Searchのコード
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));JavaでのBinary Searchのコード
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}C++でのBinary Searchのコード
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}CでのBinary Searchのコード
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}PseudocodeでのBinary Searchのコード
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger — search the right half26 lo ← mid + 127 ELSE28 // Target is smaller — search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)二分探索のよくある質問
二分探索の時間計算量はどのくらいですか？
平均ケースと最悪ケースで
O(log n) です。1回の比較ごとに残りの探索範囲が半分になるためです。最初の中央の要素が目的の値だった場合の最良ケースは O(1) です。反復版が使う追加空間は O(1) です。なぜ二分探索にはソート済み配列が必要なのですか？
半分に絞るステップは順序に依存します。目的の値と中央の要素を比較してどちらの半分を捨てられるかがわかるのは、中央より左がすべて小さく、右がすべて大きい場合だけです。未ソートのデータではこの推論が成り立ちません — 代わりに線形探索を使うか、先にソートしてください。
二分探索と線形探索の違いは何ですか？
線形探索は要素を1つずつ走査し（
O(n)）、どんな配列でも動作します。二分探索はソート済み配列の探索範囲を半分ずつ絞りますが（O(log n)）、入力がソート済みであることが必要です。要素が少なければ差はごくわずかですが、大規模になると二分探索が圧倒的に有利です。二分探索に必要な比較回数はどのくらいですか？
最大でも約
log2(n) + 1 回です。10回の比較で1,000要素、20回の比較で1,000,000要素をカバーできます。この対数的な増加こそが、ソート済みデータでの標準的な探索手法とされる理由です。二分探索の有名なオーバーフローのバグとは何ですか？
中央を
(lo + hi) / 2 で計算すると、lo + hi が型の最大値を超えたときに固定サイズ整数がオーバーフローすることがあります。安全な形は mid = lo + (hi - lo) / 2 です。Python では問題になりません（任意精度整数）が、Java/C/C++ では実際に起きた有名なバグです。二分探索と二分探索木は同じものですか？
半分に絞るという考え方は共通ですが、構造が異なります。二分探索はソート済み配列上のアルゴリズムであるのに対し、二分探索木はキーを順序どおりに保つ連結データ構造で、探索は各ノードで左または右に下っていきます。
関連リソース
その他の可視化
