二分探索
ソート済み配列への探索アルゴリズム
1. 探索パターン
| 有効な配列範囲 | 下限値 (Ka) | 上限値 (Jo) | 探索区間 |
|---|---|---|---|
| 配列(1) ～ 配列(n) | 1 | n | [1, n]（閉区間） |
| 配列(0) ～ 配列(n) | 0 | n | [0, n]（閉区間） |
| 配列(1) ～ 配列(n) （下限の初期値を0とする場合） 第６９回【４】問２ |
0 | n + 1 | [1, n + 1)（半開区間） |
2. 閉区間
📦配列(1) ～ 配列(n) 【1 ≦ index ≦ n を探索】
0
1
2
3
...
n-1
n
'初期値
Ka = 1 '下限値
Jo = n '上限値
m = Int((Ka + Jo) / 2) '中央値📦配列(0) ～ 配列(n) 【0 ≦ index ≦ n を探索】
0
1
2
3
...
n-1
n
'初期値
Ka = 0 '下限値
Jo = n '上限値
m = Int((Ka + Jo) / 2) '中央値
閉区間（m を除外する）
[ Ka ... m ... Jo ]
↓
[ Ka ... m - 1 ]
[ m + 1 ... Jo ]
中央値 m は探索済みのため、
探索範囲から除外する。
💡サンプルコード
Dim star(8) As String
Dim Ka As Integer
Dim Jo As Integer
Dim m As Integer
Dim key As String
star(1) = "おうし座"
star(2) = "かに座"
star(3) = "さそり座"
star(4) = "しし座"
star(5) = "てんびん座"
star(6) = "みずがめ座"
star(7) = "やぎ座"
star(8) = "おとめ座"
key = "しし座"
Ka = 1
Jo = 8
'探索区間 1 ≦ index ≦ n (n = 8)
Do While Ka <= Jo
m = Int((Ka + Jo) / 2)
If key = star(m) Then
Debug.Print "見つかりました : " & m
Exit Sub
ElseIf key < star(m) Then
Jo = m - 1
Else
Ka = m + 1
End If
Loop
Debug.Print "見つかりません"
3. 半開区間
📦配列(1) ～ 配列(n)・下限の初期値 = 0 【1 ≦ index < n +1 を探索】
0
1
2
3
...
n-1
n
'初期値
Ka = 0 '下限値
Jo = n + 1 '上限値
m = Int((Ka + Jo) / 2) '中央値
半開区間（m を境界として残す）
( Ka ... m ... Jo )
↓
( Ka ... m )
( m ... Jo )
中央値 m を境界として残しながら、
探索範囲を縮小する。
💡サンプルコード
Dim star(8) As String
Dim Ka As Integer
Dim Jo As Integer
Dim m As Integer
Dim key As String
star(1) = "おうし座"
star(2) = "かに座"
star(3) = "さそり座"
star(4) = "しし座"
star(5) = "てんびん座"
star(6) = "みずがめ座"
star(7) = "やぎ座"
star(8) = "おとめ座"
key = "しし座"
Ka = 0
Jo = 9
'探索区間 1 ≦ index < n + 1 (n = 8)
Do While Ka + 1 < Jo
m = Int((Ka + Jo) / 2)
If key = star(m) Then
Debug.Print "見つかった"
Exit Sub
ElseIf key < star(m) Then
Jo = m
Else
Ka = m
End If
Loop
Debug.Print "見つかりません"
4. 過去問【４】
📦出力画面
📘 ダウンロード教材について
この教材は、全国商業高等学校協会の情報処理検定の過去問題をもとに作成された、
学習支援用のマクロ付きExcelファイルです。
- マクロは 売上集計や平均点の計算など、検定形式に沿った処理を行います。
- 外部との通信やファイル操作は一切行いません。
- 教育目的で無償提供しており、改変・再配布はご遠慮ください。
ご利用の際は、マクロを有効にする必要があります。学校のPCで使用する場合は、先生にご確認ください。
| ファイル名 | サイズ (KB) | ダウンロード |
|---|---|---|
| 第７２回【４】問１.zip | 14 | |
| 第６９回【４】問２.zip | 14 | |
| 第６７回【４】問１.zip | 14 |
