N88-BASIC、C、アセンブラでBinary search
2022/1/27(木)
N88-BASIC、C、アセンブラでBinary search
Binary search(二分探索)のアルゴリズム
以後、探したい値をキーと呼ぶことにします
また、データは昇順に並び替えられているものとします
1. 要素の中央位置の値が探したい値なら終了
2. キーが中央位置の値より小ならそれより左を新たな要素にし
キーが中央位置の値より大ならそれより右を新たな要素にし
3. 1.2.を要素がなくなるまで繰り返す
となります
例
0 1 2 3 4 (要素番号)
11 15 18 20 23 (要素) … A(0) = 11, A(1) = 15, ...
から、キー15の要素番号を得るとします
L = 0, R = 4とし、M = [(L + R) /2] = 2
A(M) = A(2) = 18なので
15 < A(M)より
新たな要素はA(M)より左
L = 0, R = M-1 = 1、M = [(L + R) /2] = 0
A(M) = A(0) = 11なので
15 > A(M)より
新たな要素はA(M)より右
L = M+1 = 1, R = 1、M = [(L + R) /2] = 1
A(M) = A(1) = 15なので
15 = A(M)より要素番号1を返す
N88-BASICでは、途中経過を色付きで表示しています
n:nは検索回数
青:検索範囲外
黄:検索範囲内
白:検索中
結果
白:キーの要素番号
赤:キー以外の要素番号
途中経過で黄色の範囲が約半分ずつ狭くなっていく
様子が分かると思います
C、Assemblerでは、途中経過の表示は省いています
Enterのみの入力で終了します
NL-BASICとblg～.zip
(bsrch001.bas、bsrch001.c、bsrch001asm.c)は
このブログ(以下のリンク)からダウンロードできます
N88-BASIC、C、アセンブラでBinary search
Binary search(二分探索)のアルゴリズム
以後、探したい値をキーと呼ぶことにします
また、データは昇順に並び替えられているものとします
1. 要素の中央位置の値が探したい値なら終了
2. キーが中央位置の値より小ならそれより左を新たな要素にし
キーが中央位置の値より大ならそれより右を新たな要素にし
3. 1.2.を要素がなくなるまで繰り返す
となります
例
0 1 2 3 4 (要素番号)
11 15 18 20 23 (要素) … A(0) = 11, A(1) = 15, ...
から、キー15の要素番号を得るとします
L = 0, R = 4とし、M = [(L + R) /2] = 2
A(M) = A(2) = 18なので
15 < A(M)より
新たな要素はA(M)より左
L = 0, R = M-1 = 1、M = [(L + R) /2] = 0
A(M) = A(0) = 11なので
15 > A(M)より
新たな要素はA(M)より右
L = M+1 = 1, R = 1、M = [(L + R) /2] = 1
A(M) = A(1) = 15なので
15 = A(M)より要素番号1を返す
N88-BASICでは、途中経過を色付きで表示しています
n:nは検索回数
青:検索範囲外
黄:検索範囲内
白:検索中
結果
白:キーの要素番号
赤:キー以外の要素番号
途中経過で黄色の範囲が約半分ずつ狭くなっていく
様子が分かると思います
C、Assemblerでは、途中経過の表示は省いています
Enterのみの入力で終了します
(bsrch001.bas、bsrch001.c、bsrch001asm.c)は
このブログ(以下のリンク)からダウンロードできます
