サーチその２

リニアサーチは単純でとてもわかりやすいがもう少し高速化しようと思えばできる。
リニアサーチでは配列の範囲内で目的の数字と一致するまで、という繰り返し部分

while(n < num && a[n] != x){
    n++;
}

if(n < num){
    return n;
}

があったがここでいちいち配列の範囲をチェックするところを工夫して関数を書き直す。

int Linear2_search(int x, int *a, int num){
    int n = 0;
    int t;

    t = a[num-1];
    a[num-1] = x;

    while(a[n] != x){
        n++;
    }

    a[num-1] = t;

    if(n < num - 1){
        return n;
    }
    if(x == t){
        return n;
    }

    return NOT_FOUND;
}

ここでは目的の数値と合うかどうかだけを繰り返しの条件としているので高速化できる。
見つからない場合繰り返しが終わらないことを防ぐため、配列の最後の要素を探している数値に置き換えている。
この仕組みはたまに番兵と呼ばれる。