2

私の目標は、標準の線形検索を使用するよりもセンチネルを使用した線形検索を採用する方が好まれる理由を理解することです。

#include <stdio.h>

int linearSearch(int array[], int length) {
    int elementToSearch;
    printf("Insert the element to be searched: ");
    scanf("%d", &elementToSearch);

    for (int i = 0; i < length; i++) {
        if (array[i] == elementToSearch) {
            return i; // I found the position of the element requested
        }
    }
    return -1; // The element to be searched is not in the array
}

int main() {
    int myArray[] = {2, 4, 9, 2, 9, 10};
    int myArrayLength = 6;
    linearSearch(myArray, myArrayLength);
    return 0;
}

ウィキペディアは次のように述べています。

オーバーヘッドを削減するもう 1 つの方法は、ループ インデックスのすべてのチェックをなくすことです。これは、目的の項目自体を番兵値としてリストの最後に挿入することで実行できます。

センチネルで線形検索を実装する場合は、

array[length + 1] = elementToSearch;

ただし、検索対象の要素が見つかると、ループは配列の要素のチェックを停止します。センチネルで線形検索を使用するポイントは何ですか?

4

6 に答える 6

11

標準的な線形検索では、すべての要素を調べて配列インデックスを毎回チェックし、最後の要素に到達したときをチェックします。あなたのコードのように。

for (int i = 0; i < length; i++) {
    if (array[i] == elementToSearch) {
        return i; // I found the position of the element requested
    }
}

しかし、センチネル検索の考え方は、最後に検索する要素を保持し、配列インデックス検索をスキップすることです。これにより、各反復で 1 つの比較が削減されます。

while(a[i] != element)
    i++;
于 2015-10-25T11:58:43.947 に答える
1

配列の最後に検索する値を追加するforと、初期化、条件、およびインクリメントでループを使用する代わりに、次のような単純なループが可能になります。

while (array[i++] != ementToSearch)
    ;

次に、ループ条件は、検索する値のチェックです。つまり、ループ内で実行するコードが少なくなります。

于 2015-10-25T11:58:36.933 に答える
0

ポイントは、for ループを while/repeat ループに変換できることです。毎回 i < length をチェックしていることに注意してください。隠蔽すれば、

do {
} while (array[i++] != elementToSearch);

その後、その余分なチェックを行う必要はありません。(この場合、array.length は 1 つ大きくなります)

于 2015-10-25T11:58:41.043 に答える