game-engineer:classes:2024:game-algorithm:banpei

番兵法

線形探索

線系探索を普通にやろうと思うと、だいたいこうなるよね？

〇 検索するデータ：Key
〇 データ列の数（配列数）：N
〇 戻り値：
 　・データが見つかった時 　：データの位置(index)
 　・データが見つからない時 ：-1 (Not Foundの戻り値としてあり得ないindexを返す)
     
SequentialSearch()
 ・ i ← 0
　■ i < N and A[i] != Key 
　| ・ i ← i + 1
　■
　▲ i => N
　| ・ return -1
　+---------------
　| ・ return i
　▼

Cで書いてみるとこんな感じ

#include <stdio.h>
int main(void){
    int n = 5; //配列数
    int A[5] = {3, 1, 2, 5, 4}; //C言語ってconst int使えるんだっけ？
    int i;
    int Key = 8; //探索する数
    printf("Key = %d\n", Key);
 
    for (i = 0; i < n; i++) {
        printf("%d\n", A[i]);
        if (A[i] == Key) {
            printf("見つかりました\n");
 
            return 0;
        }
    }
 
    printf("見つかりませんでした\n");
    return 0;
}

ちなみに、疑似言語通りの動きをする関数を作るとこんな感じ（多分配列を関数に渡す云々とかやってないんだよね？）

#include <iostream>
 
/// <summary>
/// 大きさnの配列datの中からkeyのデータを探す関数
/// </summary>
/// <param name="n">配列のサイズ</param>
/// <param name="dat">配列の名前</param>
/// <param name="key">探すデータ</param>
/// <returns>
/// 戻り値  i:Keyをdat[i]で見つけた。
///        -1:見つからなかった
/// </returns>
int SequentialSearch(int n, int dat[], int key)
{
	int i = 0;
	while (i < n && dat[i] != key)
	{
		i = i + 1;
	}
	if (i >= n)
		return -1;
	else
		return i;
}
 
int main()
{
	int n = 10;
	int A[10] = { 6,3,2,9,5,4,10,1,8,7 };
	int Key = 8;
	int res = SequentialSearch(n, A, Key);
	if (res == -1)
		printf("not found\n");
	else
		printf("Data is found in A[%02d] = %02d\n", res, A[res]);
 
}

はい。改良できるところどこよ？って思うかもしれないですが、ここです。

while (i < n && dat[i] != key)

（for文で書くとその改良が見えづらいですが）繰り返しの条件が、複合条件で「配列の境界チェック」AND「キーの発見チェック」になっています。
日本語で書くと、
iでループを回すときに「配列が大きさnをオーバーしない、かつ、データの[i]は探しているキーではない」間ループを回す
になっています。逆に言うとループを抜けるのは、「iが配列の大きさnを超えたとき」または、「キーが見つかった時」に配列の添え字を返す関数です。
それ以外はエラーとして―1を返します。

ここまでは、みんな大丈夫だと思います。

番兵さん

この条件をちょい簡単にする方法を考えてみます。
やることは簡単で、「必ずどこかでKeyが見つかるようにしておく」です。今のやり方はKeyが見つからないときがあるので、配列よりも添え字がオーバーしちゃわないか
こわごわ確認しながらサーチしてます。

それを、配列の最大値（最大サーチするとこの次(N+1とする））= Keyにしておくと、

▲ A[i] == Key 
| ・ res = i
▼
▲ i == N
| ・ A[0]~A[N-1]までにKeyはなかった（Nまでサーチしちゃってる）
+---------------
| ・ A[i]でKeyは見つかった （0~N-1のどこかでKeyを見つけてある）
▼

と書くことができます。つまり、上の疑似言語の「i < N and」がいらなくなるね！

このアルゴリズムを、普通の線系探索を参考に疑似言語としてまとめて書いてみます。

番兵さん入り線形探索

〇 検索するデータ：Key
〇 データ列の数（配列数）：N+1
〇 戻り値：
 　・データが見つかった時 　：データの位置(index)
 　・データが見つからない時 ：-1 (Not Foundの戻り値としてあり得ないindexを返す)
     
SequentialSearch()
 ・ i ← 0
 ・ A[N] = Key
　■ A[i] != Key 
　| ・ i ← i + 1
　■
　▲ i == N ?
　| ・ return -1
　+---------------
　| ・ return i
　▼

なんか妙にすっきりしたね笑
最後にソース追加しておくよ

#include <iostream>
 
/// <summary>
/// 大きさnの配列datの中からkeyのデータを探す関数
/// </summary>
/// <param name="n">配列のサイズ</param>
/// <param name="dat">配列の名前</param>
/// <param name="key">探すデータ</param>
/// <returns>
/// 戻り値  i:Keyをdat[i]で見つけた。
///        -1:見つからなかった
/// </returns>
int SequentialSearch(int n, int dat[], int key)
{
	int i = 0;
	while (i < n && dat[i] != key)
	{
		i = i + 1;
	}
	if (i >= n)
		return -1;
	else
		return i;
}
 
/// <summary>
/// 大きさnの配列datの中からkeyのデータを探す関数
/// </summary>
/// <param name="n">配列のサイズ</param>
/// <param name="dat">配列の名前</param>
/// <param name="key">探すデータ</param>
/// <returns>
/// 戻り値  i:Keyをdat[i]で見つけた。
///        -1:見つからなかった
/// </returns>
int SequentialSearchSentinel(int n, int dat[], int key)
{
	dat[n] = key; //データの最後＝配列数と同じインデックスのとこ
	int i = 0;
	while (dat[i] != key)
	{
		i = i + 1;
	}
	if (i == n + 1)
		return -1;
	else
		return i;
}
 
int main()
{
	int n = 10; //これはデータ数
	//データ数＋１の配列が必要
	//一番後ろこの場合A[10]は、番兵さんが入るので空けとく
	int A[11] = { 6,3,2,9,5,4,10,1,8,7 };
	int Key = 8;
	//int res = SequentialSearch(n, A, Key);
	int res = SequentialSearchSentinel(n, A, Key);
	if (res == n)
		printf("not found\n");
	else
		printf("Data is found in A[%02d] = %02d\n", res, A[res]);
 
}