線形探索をCとC++で実行

線形探索とは？

線形探索は一致または末尾まで各要素を確認します。

未ソートデータからtargetを探します。

重要なポイント

空、1要素、重複、ソート済み入力をテストします。
正しさと最適化を分けます。
実務ではstandard libraryを優先します。

線形探索のビジュアライザー

O(n)

再生またはステップを使って、比較とデータ移動を順に確認できます。

CとC++のコード例

C

実行 →

main.c

#include <stdio.h>

int find(const int *values, int size, int target) {
    for (int index = 0; index < size; ++index) {
        if (values[index] == target) return index;
    }
    return -1;
}

int main(void) {
    int values[] = {14, 3, 27, 8, 19};
    printf("index=%d\n", find(values, 5, 8));
}

期待される出力

index=3

C++

実行 →

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector values{14, 3, 27, 8, 19};
    auto match = std::find(values.begin(), values.end(), 8);
    std::cout << "index="
              << std::distance(values.begin(), match) << '\n';
}

期待される出力

index=3

CとC++の比較

最悪O(n)です。Cは見つからない場合-1、C++はiteratorを返してendと比較します。

C

loop、pointer、length、bufferを明示します。

C++

iteratorとalgorithmが操作と格納方法を分離します。

練習課題

両方を実行して変更し、言語ごとの保証を確認します。

各比較を手で追跡します。
重複と極値をテストします。
standard libraryとbenchmarkします。