C++で線形探索を使って配列の最小要素を求めるプログラム

本記事では、線形探索（リニアサーチ）の手法を用いて、配列内の最小要素を求めるC++プログラムを紹介します。このプログラムの計算量はO(n)です。線形探索は配列の先頭から順に要素を一つずつ確認していくシンプルなアルゴリズムであり、配列がソートされている必要がないため、どのような配列にも適用できるのが特徴です。

アルゴリズム

開始
   データ要素を配列に格納する。
   インデックス「0」の値を最小値変数に代入する。
   最小値を他のデータ要素と順番に比較する。
   最小値がそのインデックスの値より大きい場合は、値を更新する。
   最小値を出力する。
終了

サンプルコード

#include<iostream>
using namespace std;
int main() {
   int n, i, minimum, a[10] = {1, 6, 7, 10, 12, 14, 12, 16, 20, 26};
   char ch;
   minimum = a[0];
   cout<<"\nThe data element of array:";
   for(i = 0; i < 10; i++) {
      cout<<" "<<a[i];
      if(minimum > a[i])
         minimum= a[i];
   }
   cout<<"\n\nMinimum of the data elements of array using linear search is: "<<minimum;
   return 0;
}

実行結果

The data element of array: 1 6 7 10 12 14 12 16 20 26
Minimum of the data elements of array using linear search is: 1

このプログラムでは、まず配列の先頭要素（インデックス0）を最小値として初期化し、その後、残りの要素を順番に比較していきます。現在の最小値より小さい要素が見つかるたびに最小値を更新することで、ループが終了した時点で配列全体の最小値が求められます。要素数をnとすると、すべての要素を一度ずつ確認するため、計算量はO(n)となります。