C・C++の線形探索
このレッスンでは、線形探索を使って、並べ替えられていない配列の中で値がある位置を見つけます。
はじめに
線形探索は、配列の先頭から要素を1つずつ調べ、探す値が見つかるか最後までたどり着くまで続けます。いちばん単純な探索アルゴリズムで、データが並べ替えられていなくても使えます。
大切なポイント
- 空のデータ、要素が1つのデータ、重複を含むデータ、並べ替え済みのデータで試しましょう。
- まず正しく動かし、最適化はその後にしましょう。
- 実際のコードでは、標準ライブラリの既製の関数を優先しましょう。
C・C++の線形探索のビジュアライザー
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=3C++
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=3CとC++の比較
どちらのバージョンも、最悪の場合の計算量はO(n)です。Cの関数findは符号付きのint型でインデックスを返すので、見つからなかったことを-1で表せます。C++のバージョンはstd::findを使い、これはイテレーターを返します。イテレーターがvalues.end()と等しければ、値は配列にありません。
C
ループ、ポインタ、長さ、一時的なバッファをすべて明示的に書きます。
C++
イテレーターと標準アルゴリズムが、処理とデータの保存方法を切り離します。
発展問題
両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。
- 比較を1回ずつ紙の上でたどってみましょう。
- 重複した値や、とても大きい値・小さい値で試しましょう。
- 自分で書いたコードの実行時間を測り、標準ライブラリと比べましょう。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ