C++で配列内の最小値と2番目に小さい値を検索する方法

n個の要素からなる配列が与えられたとき、その中で最も小さい要素(最小値)と、2番目に小さい要素を見つける必要があります。ここでいう「2番目に小さい要素」とは、最小値より大きい値の中で最小のものを指します。

この問題は、配列の各要素を先頭から順に走査しながら、現時点での最小値と2番目に小さい値を適切に更新していくことで解決できます。

アルゴリズムの考え方

まず、最小値(first)と2番目に小さい値(sec)を、それぞれ int 型の最大値 INT_MAX で初期化します。次に配列を一巡するループの中で、以下の条件に従って値を更新していきます。

• 現在の要素が最小値より小さい場合:2番目に小さい値を元の最小値で更新し、最小値を現在の要素で置き換えます。
• そうでなく、現在の要素が2番目に小さい値より小さい場合:2番目に小さい値を現在の要素で更新します。

この方法では配列を一度走査するだけで済むため、時間計算量は O(n) となり、非常に効率的です。

サンプルコード

#include<iostream>
using namespace std;
int getTwoSmallest(int arr[], int n) {
   int first = INT_MAX, sec = INT_MAX;
   for (int i = 0; i < n; i++) {
      if (arr[i] < first) {
         sec = first;
         first = arr[i];
      }else if (arr[i] < sec) {
         sec = arr[i];
      }
   }
   cout << "First smallest = " << first << endl;
   cout << "Second smallest = " << sec << endl;
}
int main() {
   int array[] = {4, 9, 18, 32, 12};
   int n = sizeof(array) / sizeof(array[0]);
   getTwoSmallest(array, n);
}

実行結果

First smallest = 4
Second smallest = 9

コードの解説

この例では、配列 {4, 9, 18, 32, 12} を走査しています。最初の要素 4 が最小値として記録され、続く要素 9 が2番目に小さい値になります。それ以降の要素(18、32、12)はどちらの条件にも該当しないため、最終的に最小値は 4、2番目に小さい値は 9 という結果が出力されます。

なお、配列内に同じ最小値が複数存在する場合は注意が必要です。上記のコードでは、2番目に小さい値として同じ値が記録される可能性があります。厳密に「異なる値」としての2番目を求めたい場合は、条件を arr[i] < sec && arr[i] != first のように変更することで対応できます。