配列内に指定の値が存在するかを探索する_2（2分探索）
gifu_shino.g線形探索法とは違い、高速に探索できる2分探索法で探索してみます。
線形探索法では、配列の先頭（または末尾）から順に探索します。
2分探索の流れについて簡単な解説です。
1.線形探索では、配列内の数値の並び順は問いませんが、
2分探索では、配列内の要素の値（数値）は昇順（降順）
であることが必須条件です。
※ここからの解説では、配列内の要素の値（数値）が
昇順であるのことが前提の解説です。
2.対象配列（最初は配列の先頭から末尾までの全体）より、
その中央位置（中央の要素位置）の配列要素の値と探索値を比較します。
この結果、
・配列要素の値と探索値とが同値であれば、探索終了となります。
不一致の場合は、
・配列要素の値より探索値の方が大きければ、中央位置より後方に。
・配列要素の値より探索値の方が小さければ、中央位置より前方に。
その探索値が存在する可能性があります。
※この時、探索値が存在するとは限りません。
3.不一致の場合、探索に必要になる配列の要素は、
・探索値の方が大きければ、中央位置より後方のみ。
※中央位置以前の配列要素は比較不要
・探索値の方が小さければ、中央位置より前方のみ。
※中央位置以降の配列要素は比較不要
となり、対象範囲の約半分の配列要素との比較が不要になります。
4.そのため、対象範囲として残った配列要素は、
・探索値の方が大きければ、
探索範囲は、中央位置の次の要素から末尾まで。
・探索値の方が小さければ、
探索範囲は、中央位置の前の要素から先頭まで。
となり、その範囲で再び中央位置を決め、2.からの処理を繰り返します。
5.この探索範囲が設定できなくなった（先頭位置＞末尾位置）とき、
探索の繰り返し（2.から4.まで）は終了となり、
ループは探索値は見つからなかったことになります。
この解説を図にしてみました。
この図は、線形探索法と2分探索法を比較したものです。
この２つの図は同値を発見できる（探索成功）場合です。
この図は同値が発見できなかった（探索失敗）場合です。
では、2分探索をプログラムしてみます。
・プロジェクトを作成します。
Visual Studio 2022を起動し、
新しいプロジェクトを作成します。
・プロジェクトタイプ："コンソールアプリ"
・プロジェクト名："ct_106_1"
とします。type
※プロジェクトの作成方法は、PCでC言語基礎編の
・２つの入力値（整数値）の四則演算結果を表示する
を参考にして下さい。
・プログラム記述・編集画面が表示されるので、
以下のプログラムを記述します。
プログラムの記述内容
// 配列内より指定の値の有無を探索する_2
// 2分探索法の利用
#include <iostream>
int main()
{
// 変数宣言と初期化
// 探索対象配列
int array[] = { 1,2,3,4,5,6,7,8,9,10 };
// 探索範囲の設定
int lo_range = 0;
int hi_range = ( sizeof(array) / sizeof(array[0])) - 1;
// 比較対象値位置設定
int median = (lo_range + hi_range) / 2;
// 探索結果位置格納
int position = -1;
// 探索数値設定
int target;
// キーボードからの探索数値を受け取る
printf("探索数値：");
scanf_s("%d", &target);
// 探索範囲を絞りながらの探索ループ
while(lo_range <= hi_range) {
// 探索値発見
if (array[median] == target) {
position = median + 1;
break;
}
// 探索値見つからず
else {
if (array[median] > target) {
hi_range = median - 1;
}
else {
lo_range = median + 1;
}
}
median = (lo_range + hi_range) / 2;
}
// 探索結果の表示
if (position == -1) {
printf("探索対象数値はありませんでした\n");
}
else {
printf("対象数値は%d番目にありました\n", position);
}
return EXIT_SUCCESS;
}
簡単なプログラム解説です。
・変数宣言と初期化
int array[] = { 1,2,3,4,5,6,7,8,9,10 };
今回、探索するため使用する配列（昇順）を宣言します。
int lo_range = 0;
探索対象範囲の配列の先頭位置の添え字を格納します。
※初回は、配列全体なので 0 を格納
int hi_range = ( sizeof(array) / sizeof(array[0])) - 1;
探索対象範囲の配列の末尾位置の添え字を格納します。
※初回は、配列全体なので、
この式によって、配列内の要素数を取得し、
末尾の要素番号なので取得値 - 1 の値を格納します。
int median = (lo_range + hi_range) / 2;
比較対象位置を設定するために中央位置を計算し格納します。
int position = -1;
探索結果とした対象が存在した場合、その添え字を格納
添え字は 0 から始まるので、探索失敗を確認できるよう
-1 を初期設定しています。
int target;
キーボートからの探索対象数値を格納
・キーボードからの探索数値を受け取る
printf("探索数値：");
scanf_s("%d", &target);
キーボードからの入力待ちがわかるよう、
画面に、"探索数値："と表示し、
キーボードからの入力を変数 target に格納します。
・探索範囲を絞りながらの探索ループ
while(lo_range <= hi_range) {
if (array[median] == target) {
position = median + 1;
break;
}
else {
if (array[median] > target) {
hi_range = median - 1;
}
else {
lo_range = median + 1;
}
}
median = (lo_range + hi_range) / 2;
}
繰り返し回数が不定なので、for( )文ではなく、
while( )文を使用します。
while( )文は、
while( 継続条件式 ) { }
という文法になります。
このwhile( )文では、
変数 lo_range と 変数 hi_range との大小関係を確認し、
lo_range ＞ hi_range となったとき、発見できなかった
として、探索ループを終了します。
※lo_range ＞ hi_range とは、
探索範囲位置の設定が、先頭位置と末尾位置が
先頭位置 ＞ 末尾位置となった状態です。
if (array[median] == target) {
この時、比較対象と探索値が一致しているかを確認し、
一致した場合、変数 position に添え字 + 1 を
発見位置として格納します。
一致しなかった場合は、
if (array[median] > target) { により、
その探索値が、中央位置（比較した配列の値）より、
前方にあるか、後方にあるかを判断し、
前方にある場合、hi_range = median - 1 とし、
対象範囲の末尾を中央位置の前方のみに設定します。
また、後方にある場合、lo_range = median + 1 とし、
対象範囲の先頭を中央位置の後方のみに設定します。
この後、繰り返しを継続します。
・探索結果の表示
if (position == -1) {
printf("探索対象数値はありませんでした\n");
}
else {
printf("対象数値は%d番目にありました\n", position);
}
ループが完了した段階で、
変数 position が -1 の場合、探索対象は見つからず、
変数 position が -1 以外の場合、探索成功で、
この変数内にその位置が格納されていますので、
変数 position を確認し、その内容に合わせ表示します。
繰り返し制御文については、
Arduino編の 制御文法を使う（反復）条件により処理を繰り返す
でもう少し詳しく解説しています
・実行してみます。
上段メニュー"デバッグ(D)"のサブメニューより、
"デバッグなしで開始(H)"を選択します。
・実行結果は、デバッグコンソール画面が開き表示されます。
※この実行では、3 を入力した例で、
"対象数値は3番目にありました"と表示されています。
※この画面は、何かのキーを打鍵することで閉じることができます。
※この実行では、13 を入力した例で、
"探索対象数値はありませんでした"と表示されています。
