【アルゴリズム入門 Q034】最小値の探索

こんにちは。ECF代表のヒガです。

本記事では初心者向けアルゴリズムの演習問題を紹介しています。日頃のプログラミング学習にご活用ください。

はじめに

アルゴリズムとは、コンピューターに行わせる計算手順のことです。自在にプログラムを作るには、プログラム言語の文法の知識とともにアルゴリズムの考え方を身につけることが必要になります。

アルゴリズム技法習得の肝は「繰り返し」の活用です。この連載では、簡単な題材で繰り返しを使うアルゴリズムの基本パターンを練習していきます。

演習問題の一覧や勉強スタイルについてのアドバイスはこちらからどうぞ。

【プログラミング初心者向け】アルゴリズム入門演習問題集〜繰り返しをマスターしよう！

こんにちは。ECF代表のヒガです。プログラミング初心者向けアルゴリズム演習問題の連載記事まとめです。日頃のプログラミング学習、講義、研修等での演習にご活用ください。「繰り返しアルゴリズム」をマスターしようアルゴリズムとは、コンピュ...

Q034 最小値の探索

配列に格納された数値データのうち、最小値とその格納位置（添字）を表示させてください。なお、同じ値が複数の配列要素に格納されている場合は、添字が小さい方を表示させてください。

初期値として {68, 55, 72, 93, 87} を使って整数型（Javaではint型）配列を準備した場合の実行例は次のとおりです。

配列で最小値「55」と、その要素の添字「1」が表示されます。

ヒント

Q033の線形探索がベースとなりますが、単に一致するものを探索するわけではなく、「ここまでの探索の中での最小値」を管理して判断していく形になります。変数をうまく使いましょう。

解答例と解説

考え方

まずは今回の主題である最小値の探索ループを考えてみましょう。ループということで、まず最初に「何を繰り返す」かを考えます。

人力で配列を前から順に見ながら最小値を探すことを想像してみましょう。具体的に {6, 4, 8, 2, 10} という配列データで考えます（より理解しやすくするために、実行例とは違う例にしてみました）。

1番目の要素「6」はとりあえず開始時の暫定最小値とします。
「6」と2番目の要素「4」を比較します。「4」の方が小さいです。暫定最小値の更新です。
「4」と3番目の要素「8」を比較します。「4」の方が小さいです。
「4」と4番目の要素「2」を比較します。「2」の方が小さいです。暫定最小値の更新です。
「2」と5番目の要素「10」を比較します。「2」の方が小さいです。
以上より、最終の確定最小値は「2」とわかりました。

説明がイメージしやすいように「暫定最小値」という表現をしてみました。前から順に比較するうちに、暫定1位が次々変わるイメージです。そして、手順2〜5が繰り返しの手順となりそうです。

手順1は繰り返しの手順というよりは、手順2から繰り返すための前準備みたいなものと見なせます。一旦暫定の最小値を「6」としておき、この値と2番目以降の要素を比較していきます。比較して配列要素の方が小さいときには暫定最小値を更新します（手順2と手順4）。

ということで、

暫定最小値と配列のデータ要素を比較する
- 配列のデータ要素の方が小さい場合、暫定最小値を更新する

という条件分岐を繰り返すことになります。

全体を箇条書きでまとめると、

配列の1番目のデータ要素を暫定最小値とする（値やその添字を管理する）
次の動作を配列の2番目の要素から最後の要素まで繰り返す
1. 暫定最小値と【カウンタ変数】番目のデータ要素を比較する
  1. 【カウンタ変数】番目のデータ要素が小さい場合、暫定最小値（値やその添字）を更新する
ここまでの暫定最小値＝最終確定の最小値とその添字を表示する

という流れになります。1番目の要素は暫定最小値として準備していますので、2番目の要素から繰り返しが始まります。

具体的な変数の割当については、次のフローチャートを確認してください。

フローチャート例

探索ループは暫定最小値更新の条件分岐を繰り返す、という形になっています。

なお、このフローチャート例では暫定最小値を管理するために変数minValueを使用していますが、この変数とは別に暫定最小値が格納された配列要素の添字（変数minIndex）を管理しているため、効率を考えると不要です。変数minValueは配列要素a[minIndex]で置き換えることができます。

Javaでの実装例

public class Q034 {
    public static void main(String[] args) {
        int[] a = {68, 55, 72, 93, 87}; // 操作対象配列の宣言と初期化
        
        int minValue = a[0]; // 暫定最小値
        int minIndex = 0; // 暫定最小値の添字
        
        for (int i = 1; i < a.length; i++) { // 探索ループ
            if (minValue > a[i]) { // 暫定最小値より小さいか
                minValue = a[i]; // 暫定最小値を更新
                minIndex = i; // 暫定最小値の添字を更新
            }
        }
        System.out.println(minValue);
        System.out.println(minIndex);
    }
}

Javaでは配列の添字は「0」からスタートしますので、カウンタ変数iの初期化や継続条件式は、上記のフローチャートからはそのように変更しています。配列の要素の添字は0から4（要素数 - 1）なので、0から4までの5回の繰り返しです。

上のフローチャートとの対応からプログラム実装例の流れを確認しましょう。

参考に、以下は変数minValueを使用しない実装例です。

public class Q034_2 {
    public static void main(String[] args) {
        int[] a = {68, 55, 72, 93, 87}; // 操作対象配列の宣言と初期化
        
        int minIndex = 0; // 暫定最小値の添字
        
        for (int i = 1; i < a.length; i++) { // 探索ループ
            if (a[minIndex] > a[i]) { // 暫定最小値より小さいか
                minIndex = i; // 暫定最小値の添字を更新
            }
        }
        System.out.println(a[minIndex]);
        System.out.println(minIndex);
    }
}

おわりに

線形探索とは少し別のバリエーションで、数値データ配列から最小値を見つけるアルゴリズムでした。「暫定最小値」という概念をもとに変数をうまく使って実現しています。

アルゴリズムの学習は、フローチャートやプログラム実装の完成形から見ると理解しづらいところがありますが、自身の経験を元にした考え方（日本語での箇条書き）からスタートすると、すんなりと理解できることがあります。もちろん個人差や学習対象のアルゴリズムの差はありますが、様々な視点からアプローチしてみることが大切です。

次回はこちらです。