[TAOCP第3巻6.1節]順次検索

TAOCPの第3巻の検索アルゴリズムで最初に述べたのは順序検索である.
シーケンス検索の利点は、データ量が十分に小さい場合に最も高速であることです.
また、無秩序データセットの場合、シーケンス検索は唯一実行可能な方法である.
まずは6.1節のプログラムS

int search(int array[],int count, int n) {
    int i = 0;
    for(; i < count; i++) {
        if(array[i] == n) {
            return i;
        }
    }
    return -1;
}

非常に簡単ですが、サイクルごとに2回比較する必要があります.
尾部に歩哨値を追加することで、比較回数を1回に下げることができます.
これが6.1節のアルゴリズムQである.

int search(int array[],int count, int n) {
    int i = 0;
    int t = array[count];  //       ，     
    array[count] = n;
    for(; array[i] != n; i++) {
    }
    array[count] = t; //    
    if(i < count) {
        return i;
    else {
        return -1;
    }
}

nが大きいとアルゴリズムSより少し速くなります.しかしarrayの尾に余分な空間が必要で、
メモリの割り当てには注意が必要です.
アルゴリズムQには最適化版Q′がある

int search(int array[],int count, int n) {
    int i = 0;
    int t = array[count];  
    array[count] = n;
    while(1) {
        if(array[i] == n) {
            break;
        }
        if(array[i+1] == n) {
            i++;
            break;
        }
        i += 2
    }
    array[count] = t; 
    if(i < count) {
        return i;
    else {
        return -1;
    }
}

一度に2歩進むのは、手作業のループ展開でしょう.
ただしgccは-O 3パラメータを使用すると自動的にループ展開し、
この仕事はやはりコンパイラに残しておきましょう.
データが順序付けされている場合、アルゴリズムTを使用することができる.

int search(int array[],int count, int n) {
    int i = 0;
    int t = array[count];  
    array[count] = INT_MAX;  //      array      
    for(; array[i] < n; i++) {
    }
    
    array[count] = t; 
    
    //array[i] >= n
    if(i < count && array[i] == n) {  //        
        return i;
    else {
        return -1;
    }
}

検索に成功するとアルゴリズムTはアルゴリズムQと同じくらい速く、
しかし失敗したときTはQの約2倍だった.
秩序化されたデータについては、より高速な二分検索を使用できます.
しかし、すべての場合、二分検索が速いわけではありません.
データ総数Nが比較的小さい場合、アルゴリズムTはより速く、Tはより簡単である.