【C#で学ぶ】応用情報技術者試験のためのアルゴリズム入門

こんにちは！今回は応用情報技術者試験（AP）の受験者を対象に、試験でよく出題される「アルゴリズム」の基礎を筆者と共に学びましょう。アルゴリズムはプログラミングの根幹であり、試験でも重要なトピックです。この記事では、代表的なアルゴリズムである「線形探索」と「二分探索」を取り上げ、筆者の得意なC#で実装例を挙げていきます。

アルゴリズムとは？

アルゴリズムとは、問題を解くための手順や計算方法のことです。たとえば、「部屋にある本の中から特定のタイトルを探す」という課題があった場合、「本を1冊ずつ確認する」という方法もアルゴリズムの一種です。応用情報技術者試験では、効率的なアルゴリズムを選ぶ能力や、その仕組みを理解する力が求められます。

試験では以下のようなトピックが頻出です：

• 探索アルゴリズム（線形探索、二分探索）
• 整列アルゴリズム（バブルソート、クイックソートなど）
• 時間計算量（O記法）

ここでは、探索アルゴリズムを中心に解説します。

1. 線形探索（Linear Search）

概要

線形探索は、配列やリストの要素を先頭から順番に調べていくシンプルな方法です。目的の値が見つかるまで1つずつ確認するため、単純ですがデータ量が多いと時間がかかります。

特徴

• 時間計算量: O(n)（nは要素数）
• メリット: 実装が簡単、ソートされていないデータでも使える
• デメリット: データ量が多いと非効率

C#での実装例

以下は、配列から特定の値を検索する線形探索のコードです。

using System;

class Program
{
    static int LinearSearch(int[] array, int target)
    {
        for (int i = 0; i < array.Length; i++)
        {
            if (array[i] == target)
            {
                return i; // 見つかったインデックスを返す
            }
        }
        return -1; // 見つからなかった場合は-1を返す
    }

    static void Main()
    {
        int[] numbers = { 4, 2, 7, 1, 9, 5 };
        int target = 7;

        int result = LinearSearch(numbers, target);
        if (result != -1)
        {
            Console.WriteLine($"値 {target} はインデックス {result} にあります。");
        }
        else
        {
            Console.WriteLine($"値 {target} は見つかりませんでした。");
        }
    }
}

実行結果

値 7 はインデックス 2 にあります。

2. 二分探索（Binary Search）

概要

二分探索は、ソート済みのデータに対して使える効率的な探索方法です。配列の中央値を確認し、目的の値がそれより大きいか小さいかを判断して探索範囲を半分に絞り込む、という手順を繰り返します。

特徴

• 時間計算量: O(log n)
• メリット: 大量のデータでも高速に動作
• デメリット: データがソート済みである必要がある

C#での実装例

以下は、ソート済み配列で二分探索を行うコードです。

using System;

class Program
{
    static int BinarySearch(int[] array, int target)
    {
        int left = 0;
        int right = array.Length - 1;

        while (left <= right)
        {
            int mid = (left + right) / 2;

            if (array[mid] == target)
            {
                return mid; // 見つかったインデックスを返す
            }
            else if (array[mid] < target)
            {
                left = mid + 1; // 右半分を探索
            }
            else
            {
                right = mid - 1; // 左半分を探索
            }
        }
        return -1; // 見つからなかった場合は-1を返す
    }

    static void Main()
    {
        int[] numbers = { 1, 2, 4, 5, 7, 9 }; // ソート済み配列
        int target = 5;

        int result = BinarySearch(numbers, target);
        if (result != -1)
        {
            Console.WriteLine($"値 {target} はインデックス {result} にあります。");
        }
        else
        {
            Console.WriteLine($"値 {target} は見つかりませんでした。");
        }
    }
}

実行結果

値 5 はインデックス 3 にあります。

試験対策のポイント

1. アルゴリズムの流れを理解する
   試験では疑似コードやフローチャートが出題されることがあります。コードを読む前に、手動でアルゴリズムをシミュレーションしてみましょう。
2. 時間計算量を押さえる
   O(n)やO(log n)の意味を理解し、どのアルゴリズムが効率的かを説明できるようにしましょう。
3. ソートの有無を確認
   二分探索はソート済みデータが前提なので、問題文の条件をよく読みましょう。

おわりに

今回は線形探索と二分探索をC#で実装しながら学びました。これらは応用情報技術者試験だけでなく、実務でも役立つ基本的なアルゴリズムです。ぜひ手を動かしてコードを書き、動作を確認してみてください。試験対策としては、過去問でアルゴリズム関連の問題を解きながら感覚を掴むのがおすすめだそうです。ともに頑張りましょう！