全探索・探索・計算量

アルゴリズム問題では、コードを書く前に入力の大きさと必要な処理回数を考えることが重要です。

全探索

全探索は、考えられる候補をすべて調べる方法です。候補数が小さいとき、確実で実装しやすい解法になります。

int[] values = { 4, 7, 2, 9, 5 };
int target = 9;
bool found = false;

foreach (int value in values)
{
    if (value == target)
    {
        found = true;
        break;
    }
}

Console.WriteLine(found ? "Found" : "Not Found");

計算量

要素数をNとすると、配列を1回走査する処理はO(N)、二重ループで全組み合わせを調べる処理は一般にO(N^2)です。

二分探索

ソート済み配列では、中央の値と比較して探索範囲を半分ずつにできます。計算量はO(log N)です。

int[] values = { 2, 4, 7, 9, 12, 15 };
int target = 9;
int left = 0, right = values.Length - 1, answer = -1;

while (left <= right)
{
    int mid = left + (right - left) / 2;
    if (values[mid] == target) { answer = mid; break; }
    if (values[mid] < target) left = mid + 1;
    else right = mid - 1;
}
Console.WriteLine(answer);

二分探索にはデータがソート済みであるという前提があります。前提条件を満たしていないデータに適用してはいけません。