線形探索

探索とは、データの集合から特定の値を見つける操作のことです。

例えば、データの中から

  • 男性
  • 21歳から29際の人
  • 年収500万円未満の人

を探す操作になります。

ここでは、ランダムなデータの並びから目的のデータを見つける際に有効な線形探索を紹介します。

線形探索の手順

線形探索では、ランダムな並びのデータをはじめから片っ端にチェックしていく方法です。

例えば、

3,2,5,2,1,4,9,1,3,5

から「9」を探索するには、

  • 3,2,5,2,1,4,9,1,3,5
  • 3,2,5,2,1,4,9,1,3,5
  • 3,2,5,2,1,4,9,1,3,5
  • 3,2,5,2,1,4,9,1,3,5
  • 3,2,5,2,1,4,9,1,3,5
  • 3,2,5,2,1,4,9,1,3,5
  • 3,2,5,2,1,4,9,1,3,5 <–発見!

とすればOKです。もし、最後まで目的の値がなければ探索失敗です。線形探索の計算回数はデータ数をnとすれば、平均でn/2回です。

あと、線形探索は、順番に探すので逐次探索とも呼ばれます。

線形探索のコーディング

では、線形探索のコーディングを行います。以下のように組めば、線形探索を実現できます。

int senkei(int a[],int n,int target){
    int i=0;
	while(true){
	    if(i==n){
		    return -1;
		}
		if(a[j]==target){
		    return i;
		}
		i++;
	}
}

著者:安井 真人(やすい まさと)