値の検索(リニアサーチ)
ゲームを作っていると配列等の値を検索する必要がある事が多々あります。
そんな時に使える一番原始的な検索アルゴリズムにリニアサーチ(線形検索)があります。
配列の中からデータを探す際に誰でも思いつく検索処理がこれだと思います。
アルゴリズム
リニアサーチのアルゴリズムは至極単純です。
先頭のデータから末尾のデータまで順番に値を比較していきます。
一致するデータが見つかったタイミングでデータを返すという仕組みです。
実装方法
int型のデータの中から指定した値を探すには下記のようになります。
// リニアサーチを使った検索
int LinearSearch(int* pData, int count, int value)
{
for (int i = 0; i < count; i++)
{
if (pData[i] == value)
{
return i;
}
}
return -1;
}
これでcount個のint型データが入ったpDataの中からvalueと一致する値が検索できます。
見つからない場合は-1が返ります。
使い方
実際に使う時は下記のようになります。
// 検索するデータリスト
int data[] = { 5, 15, 3, 6, 7, 8, 20, 31 };
// サーチテスト
void SearchTest()
{
int find = 7;
int index = LinearSearch(data, sizeof(data) / sizeof(*data), find);
printf("LinearSearch:%d\n", index);
}
これでdataの配列の中からfind(7)が入ったインデックスを検索して取得できます。
今回の場合は4番目の配列に7があるので
LinearSearch:4
と表示されます。
検索処理はゲーム内でも多用する処理なので
基本のリニアサーチは必ず覚えておきましょう。