アルゴリズム,番兵を使用して線形探索を行う

スポンサーリンク

鍛錬 931

アルゴリズム,番兵を使用して線形探索を行う

線形探索を行う方法の一つとして、番兵を使用する方法があります。

番兵のアルゴリズムを使用することにより、「現在探索している配列の要素が、配列の上限に達していないか」等の条件判断を省き、効率的な探索を行うことが可能です。

計算量

以下は、番兵の計算量です。

O(N)
スポンサーリンク

プログラム

以下は、指定した数値が配列に存在するかどうかの探索を行うプログラム、test_sentinel.c です。

今回のプログラムはC言語で作成し、配列内の数値を探索する際に番兵を使用しています。

項目 内容
配列のサイズ int array[101]
番兵の格納位置 array[100]
検索対象の数値を格納する位置 array[77]
検索範囲 array[0] ~ array[100]
// include
#include <stdio.h>
#include <stdlib.h>

// preprocessor
#define SENTINEL 100
#define ELEMENT_MAX (SENTINEL + 1)

// prototype
int CheckNum(int *array, int target);

// main
int main(void)
{
	int *array, *p;
	int target;
	int ret;
	
	// メモリ領域を確保
	p = (int *)calloc(ELEMENT_MAX, sizeof(int));
	if (p == NULL) {
		printf("ERROR,calloc\n");
		exit(EXIT_FAILURE);
	}
	array = p;
	
	// 今回検索する数値を格納
	target = 123;
	array[77] = target;
	
	// 番兵(今回探索する数値123)を設定
	array[SENTINEL] = target;
	
	// 数値を検索
	ret = CheckNum(array, target);
	if (ret == -1) {
		printf("数値 %d は存在しません\n", target);
	}
	else {
		printf("数値 %d は array[%d] に存在します\n", target, ret);
	}
	
	// メモリ領域を解放
	free(p);
	
	return 0;
}

// ============================================
// @brief  指定した数値を検索する
// @param  array  [in],確認対象の配列
// @param  target [in],存在を確認する数値
// @return i  -> 存在する:配列の要素番号
// @return -1 -> 存在しない
// @note   無し
// ============================================
int CheckNum(int *array, int target)
{
	int i;
	
	i = 0;
	while (array[i] != target) {
		i++;
	}
	if (i < SENTINEL) {
		return i;
	}
	else {
		return -1;
	}
}
スポンサーリンク

実行結果

以下は、プログラム test_sentinel.c を実行しています。

***@ubuntu:~/***/test/c$ 
***@ubuntu:~/***/test/c$ gcc -Wall -Wextra test_sentinel.c -o test_sentinel
***@ubuntu:~/***/test/c$ ./test_sentinel
数値 123 は array[77] に存在します

 
上記に示した通り、番兵を使用して線形探索を行うことができました。

タイトルとURLをコピーしました