線形探索について

線形探索は先頭から順番に探す値が見つかるまで探していくアルゴリズム

まずは上記の図をそのままプログラムにしてみます。


# include <stdio.h>
int main(void){
    int n = 6;
    int a[6] = {5, 2, 1, 8, 6, 3};
    int i;
    int search = 8;
    printf("検索対象 = %d\n", search);
    
    for (i = 0; i < n; i++) {
        printf("%d\n", a[i]);
        if (a[i] == search) {
            puts("見つかりました");
            return 0;
        }
    }
    
    puts("見つかりませんでした");
    return 0;
}

出力結果

terminal

5
2
1
8
見つかりました

番兵法

配列の末尾に探したい値を入れておき、必ず条件式がTrueになるようにすることです。

上記の図をそのままプログラムにしてみます。


# include <stdio.h>
int main(void){
    int n = 6;
    int a[7] = {5, 2, 1, 8, 6, 3};
    int i = 0;
    int search = 9;
    printf("検索対象 = %d\n", search);
    
    a[n] = search;
    while (a[i] != search) {
        printf("%d\n", a[i]);
        i++;
    }
    
    if (i == n) {
        puts("見つかりませんでした");
        return 0;
    }
    
    printf("%d\n", a[i]);
    puts("見つかりました");
    return 0;
}

出力結果

terminal

検索対象 = 9
5
2
1
8
6
3
見つかりませんでした

まとめ

番兵使用することで、最後は必ず検索に引っかかるので、ループ条件と検索条件を組み合わせることができるようになります。
最初のfor文を使用した例だと、繰り返し条件i < nと検索マッチ条件a[i] == searchが必要だったのに比べ、
番兵を使用すると、a[i] != searchこの条件だけで良くなります。

よって、番兵を使用することで、条件式の実行回数が減る（CPUの計算量が減る）のでその分処理が高速になります。

※c言語始めたばかりなので、もっといい書き方ありそう。