【基本情報】探索アルゴリズム完全攻略｜線形探索・二分探索を図解で理解
探索の途中で値を見失う方へ：線形探索を自分で追う無料例題で、見つかった時点のreturnと、見つからない場合の終了条件を確かめられます。まず途中の値を書いてから、この下の探索手法の比較へ進んでください。
「線形探索と二分探索の違いがよく分からない……😇」
「二分探索で、なぜデータを整列する必要があるの？」
「擬似言語になると急に読めなくなる……」
基本情報技術者試験の科目Bを勉強していると、必ず押さえておきたいのが、
探索アルゴリズム
です。
探索とは、簡単にいうと、
「たくさんのデータの中から、目的のデータを探す処理」
のこと。
その代表が、
線形探索
と
二分探索
です。
まずは、この違いだけ覚えてください👇
この記事では、
探索の基本 → 線形探索 → 二分探索 → 擬似言語 → トレース → 計算量 → 練習問題
の順番で解説します。
科目B対策として、
「コードを見たときに処理を追える状態」
を目指しましょう🔥
⸻
1．そもそも「探索」とは？
探索とは、
複数のデータの中から目的のデータを探すこと
です。
例えば、次の配列があるとします。
data = [10, 30, 20, 50, 40]
この中から、
50
を探したいとします。
人間なら見ただけで、
「4番目に50がある」
と分かります。
しかし、コンピュータでは、
どのような手順で50を探すのか
を決める必要があります。
この「探し方」が、
探索アルゴリズム
です。
⸻
2．代表的な2つの探索方法
基本情報でまず押さえておきたいのが、
線形探索
先頭から1個ずつ確認する
二分探索
探索範囲を半分ずつ絞っていく
という2つです。
イメージすると、
一方、二分探索は、
というイメージです。
⸻
3．線形探索とは？
線形探索（Linear Search）は、
データを先頭から順番に1個ずつ確認する探索方法
です。
例えば、
data = [3, 8, 5, 2, 9]
から、
2
を探してみます。
先頭から確認すると、
3 → 違う
8 → 違う
5 → 違う
2 → 発見！
となります。
非常にシンプルですね。
⸻
4．線形探索を図で理解する
配列を、
とします。
探したい値は、
2
です。
探索の流れは、
data[0] = 3
↓
2ではない
data[1] = 8
↓
2ではない
data[2] = 5
↓
2ではない
data[3] = 2
↓
発見！
となります。
したがって、
添字3
に目的の値があります。
⸻
5．線形探索の特徴
線形探索のメリットは、
データが並んでいなくても使える
ことです。
例えば、
[40, 10, 70, 20, 50]
のようにバラバラでも問題ありません。
先頭から、
40 → 10 → 70 → 20 → 50
と確認すればいいからです。
つまり、
事前の整列が不要
です。
⸻
6．線形探索の弱点
一方で、線形探索には弱点があります。
それは、
データ数が増えると確認回数も増えやすい
こと。
例えば100万件のデータがあり、目的の値が最後にあれば、
最悪の場合、
100万件近く確認
することになります。
そこで登場するのが、
二分探索
です。
⸻
7．線形探索の擬似言語
線形探索の考え方を簡単な擬似言語で表すと、次のようになります。
for i = 0 to データ数 - 1
if data[i] = target
return i
endif
endfor
return -1
ここで、
target
は探したい値です。
処理の流れは、
i = 0
↓
data[0]とtargetを比較
↓
違えばiを増やす
↓
data[1]と比較
↓
……
↓
一致したら終了
です。
⸻
8．線形探索をトレースしてみる
次のデータから、
target = 7
data = [4, 9, 7, 2]
7を探します。
したがって、
i = 2
で発見します。
このように、
変数iとdata[i]を1回ずつ追う
だけでOKです。
⸻
9．線形探索の計算量
線形探索の計算量は、
O(n)
です。
なぜなら、データがn個ある場合、
最悪では、
n個すべて確認する可能性がある
からです。
例えば、
n = 10
→ 最大10個程度確認
n = 100
→ 最大100個程度確認
n = 1,000
→ 最大1,000個程度確認
となります。
データ数に比例して処理量が増えるイメージです。
⸻
10．二分探索とは？
二分探索（Binary Search）は、
探索範囲を半分ずつ絞り込んで目的のデータを探す方法
です。
ここで非常に重要なのが、
基本的にデータが整列されている必要がある
こと。
例えば、
[10, 20, 30, 40, 50, 60, 70]
のように、小さい順に並んでいるデータを考えます。
ここから、
60
を探します。
⸻
11．二分探索は「真ん中」を見る
最初に確認するのは、
中央のデータ
です。
探しているのは、
60
です。
60は40より大きいですね。
ということは、
10 20 30
側には60はありません。
そこで、
左半分を探索対象から外します。
残るのは、
50 60 70
です。
⸻
12．さらに半分にする
残った、
[50, 60, 70]
の中央を見ると、
です。
探している値と一致しました。
つまり、
2回程度の比較で60を発見
できました。
線形探索なら、
10
20
30
40
50
60
と6回確認する可能性があります。
二分探索なら、
40
↓
60
です。
この、
「不要な半分を一気に捨てる」
という考え方が重要です。
⸻
13．なぜ整列が必要なの？
ここは試験でも重要です。
例えば、
[30, 70, 10, 60, 20, 50, 40]
というバラバラのデータを考えます。
中央が、
60
だったとして、
探したい値が、
50
だったとします。
50は60より小さいですが、
50が必ず左側にあるとは限りません。
実際には右側にあります。
つまり、データがバラバラだと、
「中央より小さいから左側」
という判断ができません。
だから二分探索では、
整列済みデータ
が基本条件になります。
⸻
14．二分探索で使う3つの位置
二分探索では、次の3つを意識します。
left
探索範囲の左端
right
探索範囲の右端
mid
探索範囲の中央
イメージすると、
です。
この3つを更新しながら探索します。
⸻
15．中央位置midの求め方
中央位置は基本的に、
mid = (left + right) ÷ 2
で考えます。
例えば、
left = 0
right = 6
なら、
mid = (0 + 6) ÷ 2
= 3
です。
つまり、
data[3]
を確認します。
整数の添字として扱う場合は、問題文の規則に従って整数化します。
⸻
16．二分探索の基本ルール
中央の値とtargetを比較して、
data[mid] = target
発見
data[mid] < target
targetはもっと大きい。
→ 右半分を探す
data[mid] > target
targetはもっと小さい。
→ 左半分を探す
です。
この3パターンを覚えれば、二分探索の基本はOKです。
⸻
17．二分探索の擬似言語
簡略化すると、次のような形になります。
left ← 0
right ← データ数 - 1
while left ≦ right
mid ← (left + right) ÷ 2
if data[mid] = target
return mid
elseif data[mid] < target
left ← mid + 1
else
right ← mid - 1
endif
endwhile
return -1
一気に見ると難しく感じますが、
やっていることは、
中央を見る → 左右どちらかを捨てる
だけです。
⸻
18．二分探索をトレースしてみる
次の配列から、
target = 70
data = [10,20,30,40,50,60,70,80,90]
を探してみましょう。
添字は、
です。
最初は、
left = 0
right = 8
なので、
mid = 4
です。
data[4] = 50
70 > 50なので、
右側を探索
します。
次は、
left = 5
right = 8
となります。
中央を整数化して、
mid = 6
とすると、
data[6] = 70
です。
発見しました。
⸻
19．トレース表にすると簡単
先ほどの処理を表にすると、
となります。
科目Bでは、二分探索を頭の中だけで追うより、
left・right・midの表を書く
のがおすすめです。
⸻
20．見つからない場合はどうなる？
例えば、
data = [10,20,30,40,50]
から、
35
を探すとします。
探索を続けても35はありません。
二分探索では範囲を狭めていき、
最終的に、
left > right
となれば、
探索対象がなくなった
と判断できます。
そのため、
while left ≦ right
という条件がよく使われます。
⸻
21．線形探索と二分探索を比較
改めて整理します。
試験では特に、
二分探索＝整列済み＋半分ずつ
をセットで覚えてください。
⸻
22．二分探索の計算量
二分探索の計算量は、
O(log n)
です。
なぜなら、探索するたびに範囲が、
n
↓
n / 2
↓
n / 4
↓
n / 8
↓
……
と半分になっていくからです。
例えば1024個のデータがあっても、
1024
↓
512
↓
256
↓
128
↓
64
↓
32
↓
16
↓
8
↓
4
↓
2
↓
1
というように、
約10回程度
まで絞れます。
なぜ10回なのかというと、
2¹⁰ = 1024
だからです。
⸻
23．O(n)とO(log n)の違い
データ数が増えるほど差が大きくなります。
例えば単純化して考えると、
※これは計算量の増え方を理解するためのイメージです。実際の比較回数などは条件によって異なります。
ここから分かるのは、
データ量が大きいほど、半分ずつ絞る効果が大きい
ということです。
⸻
24．二分探索と2の累乗
二分探索を理解するうえで、
2の累乗
はかなり重要です。
最低限、
2⁰ = 1
2¹ = 2
2² = 4
2³ = 8
2⁴ = 16
2⁵ = 32
2⁶ = 64
2⁷ = 128
2⁸ = 256
2⁹ = 512
2¹⁰ = 1024
あたりは覚えておくと便利です。
二分探索だけでなく、
2進数
メモリ容量
IPアドレス
アルゴリズム
などでも役立ちます。
⸻
25．よくある間違い① 二分探索を未整列データに使う
例えば、
[50,10,80,20,40]
というデータ。
この状態では、
中央の値との大小関係だけで左右を捨てられません。
二分探索が出たら、
まず、
「整列されているか？」
を確認しましょう。
⸻
26．よくある間違い② midを確認した後も残す
例えば、
data[mid] < target
だったとします。
このとき、
left ← mid
ではなく、
left ← mid + 1
とする形が基本です。
なぜなら、
midの位置はすでに確認済み
だからです。
同様に左側を探索するなら、
right ← mid - 1
です。
⸻
27．よくある間違い③ left・right・midを頭だけで追う
二分探索でありがちなミスです。
left
right
mid
の3つが何度も変化します。
頭の中だけで追うと、
添字を1つずらすミス
が起きやすくなります。
おすすめは必ず、
のように書くこと。
これは科目Bの他のトレース問題でも使えるテクニックです。
⸻
28．よくある間違い④ 値と添字を混同する
例えば、
の場合、
data[2]
は、
2ではありません。
答えは、
30
です。
2 = 添字
30 = 値
です。
探索問題では、
「添字」と「格納されている値」
を分けて考えましょう。
⸻
29．よくある間違い⑤ O(log n)を難しく考えすぎる
基本情報レベルではまず、
O(n)
→ データ数に比例
O(log n)
→ 半分ずつ減る
というイメージを持てればOKです。
例えば、
16
↓
8
↓
4
↓
2
↓
1
と半分ずつ減るなら、
log₂16 = 4
です。
⸻
30．線形探索の練習問題
次の配列があります。
data = [5, 8, 2, 9, 4]
線形探索で、
target = 9
を探します。
何回目の比較で見つかるでしょうか？
⸻
答え
4回目
です。
5 → ×
8 → ×
2 → ×
9 → ○
となります。
⸻
31．線形探索の練習問題②
data = [7, 4, 1, 8, 3]
から、
target = 3
を探します。
添字はいくつでしょう？
⸻
答え
4
です。
data[4] = 3
ですね。
0から始まる添字には注意しましょう。
⸻
32．二分探索の練習問題①
次の整列済み配列があります。
data = [10,20,30,40,50,60,70]
targetは、
60
です。
最初に確認する中央の値は、
40
です。
60 > 40なので、
どちらを探索するでしょうか？
⸻
答え
右側
です。
50,60,70
が次の探索範囲になります。
⸻
33．二分探索の練習問題②
data = [10,20,30,40,50,60,70]
targetが、
20
だったとします。
最初の中央は、
40
です。
20 < 40なので、
左半分
を探索します。
10,20,30
ですね。
次の中央は、
20
なので発見です。
⸻
34．二分探索の練習問題③
次の配列があります。
data = [10,20,30,40,50,60,70,80,90]
targetは、
80
です。
初期状態を、
left = 0
right = 8
とします。
1回目
mid = 4
data[4] = 50
80 > 50なので、
left = 5
2回目
整数化のルールに従い、
mid = 6
data[6] = 70
80 > 70なので、
left = 7
3回目
mid = 7
data[7] = 80
一致。
したがって、
添字7
で発見です。
⸻
35．科目Bで探索問題が出たときの解き方
探索問題を見たら、次の順番で確認すると整理しやすいです。
STEP1
何を探しているか確認
target = ?
↓
STEP2
線形探索か二分探索か確認
↓
STEP3
二分探索なら、
データが整列済みか確認
↓
STEP4
添字を書く
↓
STEP5
変数を表にする
i
または、
left / right / mid
↓
STEP6
1回ずつ処理を実行
↓
STEP7
変数が変わったら必ず更新
これだけでも、トレースミスをかなり減らせます。
⸻
36．問題文を読んだら「配列」を書く
例えば、
data = [10,20,30,40,50]
とあったら、
問題用紙に、
添字 0 1 2 3 4
値 10 20 30 40 50
と書いてしまうのがおすすめです。
さらに二分探索なら、
L M R
↓ ↓ ↓
10 20 30 40 50
のように、
left・mid・right
を書き込みます。
⸻
37．線形探索は「i」を追う
線形探索なら、
基本的には、
iがどう変化するか
を追います。
i = 0
↓
i = 1
↓
i = 2
↓
……
そのたびに、
data[i]
を確認します。
つまり、
i → data[i] → targetと比較
の繰返しです。
⸻
38．二分探索は「L・M・R」を追う
二分探索では、
L = left
M = mid
R = right
と短く書くのもおすすめです。
例えば、
L=0
M=4
R=8
↓
L=5
M=6
R=8
のように追います。
問題用紙で素早く書けるので便利です。
⸻
39．探索とソートの関係
二分探索では、
整列済みであること
が重要でした。
この、
データを順番に並べる処理
を、
ソート（整列）
といいます。
例えば、
30,10,50,20,40
を昇順にすると、
10,20,30,40,50
です。
この状態なら、二分探索を利用できます。
つまり、
ソート
↓
整列済みデータ
↓
二分探索
というつながりがあります。
探索とソートはセットで勉強すると理解しやすいです。
⸻
40．科目Bでは「コードを暗記しない」
探索アルゴリズムを勉強するとき、
擬似言語を丸暗記する必要はありません。
重要なのは、
for
↓
順番に確認
↓
線形探索
や、
midを確認
↓
左右どちらかを捨てる
↓
二分探索
という、
処理の意味を理解すること
です。
コードが少し変わっても、
「何をしている処理なのか」
が分かれば対応できます。
⸻
41．探索アルゴリズム重要キーワード
ここまでの内容をまとめます。
⸻
42．試験直前チェックリスト
試験前に、次の項目を確認してみてください👇
☐ 線形探索の仕組みを説明できる
☐ 二分探索の仕組みを説明できる
☐ 線形探索では整列が不要と分かる
☐ 二分探索では基本的に整列が必要と分かる
☐ 線形探索＝O(n)と分かる
☐ 二分探索＝O(log n)と分かる
☐ targetの意味が分かる
☐ left・right・midの意味が分かる
☐ data[i]の意味が分かる
☐ 添字と値を区別できる
☐ left・right・midをトレースできる
☐ data[mid] < target のとき右側へ進める
☐ data[mid] > target のとき左側へ進める
☐ 2の累乗をある程度覚えている
☐ 探索とソートの関係を理解している
怪しいところがあれば、その部分だけもう一度確認しましょう。
⸻
43．最後にこれだけ覚える
時間がない人は、
この表だけでも押さえてください👇
さらに短く覚えるなら、
線形探索 → 1個ずつ探す → O(n)
二分探索 → 半分ずつ絞る → O(log n)
です🔥
⸻
まとめ
探索アルゴリズムで最初に押さえたいのは、
線形探索と二分探索の違い
です。
線形探索は、
A → B → C → D → …
と、
先頭から1個ずつ確認
します。
一方、二分探索は、
全体
↓
1/2
↓
1/4
↓
1/8
↓
……
と、
探索範囲を半分ずつ絞ります。
そのため、
線形探索＝O(n)
二分探索＝O(log n)
となります。
そして二分探索で忘れてはいけないのが、
基本的に整列済みデータが必要
という点です。
科目Bで擬似言語として出てきても、
線形探索
→ iとdata[i]を追う
二分探索
→ left・right・midを追う
と整理すれば、一気に読みやすくなります。
探索問題は頭の中だけで解こうとせず、
添字を書く → 変数を書く → 1処理ずつトレースする
を徹底してみてください🔥
⸻
📚 基本情報技術者試験を勉強している方へ
このnoteでは、
「基本情報の難しいテーマを、初学者でも理解できる形にする」
をテーマに、科目A・科目Bの攻略記事を公開しています。
今回の探索アルゴリズムが理解できたら、次は、
ソートアルゴリズム
へ進むのがおすすめです。
バブルソート・選択ソート・挿入ソートまで理解すると、探索と合わせて科目Bのアルゴリズム分野がかなりつながってきます。
試験前に見返せるよう保存して活用ください📌
役に立ったら、スキ・フォローしてもらえると嬉しいです🙌
