線形探索

ホームアルゴリズム入門講座 > 線形探索

線形探索

線形探索の基本データ

線形探索のアルゴリズム

線形探索はアルゴリズムの中でもっとも単純です。アルゴリズムといえるのかどうかも分かりませんが、探索の基本はすべて線形探索にあります。

線形探索を一言で言い表せば、「最初から順番に調べる」です。

線形探索の実装

using System;

namespace NewWorld
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int[] data = {6,3,8,5,4,7,9,5,1};
			
			int indexof = IndexOf(data, 5);
			int lastindexof = LastIndexOf(data,5);
			bool[] allindexof = AllIndexOf(data,5);
			
			Console.WriteLine("IndexOf = {0}", indexof);
			Console.WriteLine("LastIndexOf = {0}", lastindexof);
			
			Console.Write("AllIndexOf = ");
			for(int i=0;i<allindexof.Length;i++)
				if(allindexof[i]) Console.Write(i + " ");
		}
		
		public static int IndexOf(int[] data, int search_number)
		{
			int i;
			for(i=0;i<data.Length;i++)
				if(data[i] == search_number) break;
			
			if(i != data.Length) return i;
			else return -1;
		}
		
		public static int LastIndexOf(int[] data, int search_number)
		{
			int i;
			for(i=data.Length-1;0<=i;i--)
				if(data[i] == search_number) break;
			
			if(i != data.Length) return i;
			else return -1;
		}
		
		public static bool[] AllIndexOf(int[] data, int search_number)
		{
			int i;
			bool[] allindex = new bool[data.Length];
			for(i=0;i<data.Length;i++)
			{
				if(data[i] != search_number) allindex[i] = false;
				else allindex[i] = true;
			}
				
			return allindex;
		}
	}
}

探索の基本から説明します。

配列は

配列名[index] = value

によって構成されます。indexが分かればvalueは一発で取得できますが、valueからindexを求めるには探索が必要です。

たとえば上記の例では「配列中で 5 になっている要素を 10 に置き換えたい」というとき、value = 5 は分かっていますが、それに対応する index が分からない限り、value は置き換えることができません。探索を使うのはこのような場面です。

単なる線形探索だけではあまりにも面白くないので、ここでは3つの線形探索アルゴリズムを書いてみました。

これらはいずれも非常に簡単に実装できます。ただし、AllIndexOf()メソッドを実装する場合は、外部領域が一定以上必要です。ここでは bool 型を使うことによって外部領域を抑えています。

なお、C#では System.Collections名前空間に ArrayListクラスが実装されており、それらには検索機能が備わっています。また、ArrayListクラスを使えば、AllIndexOf()メソッドもより簡潔に記述できます。

public static ArrayList AllIndexOf(int[] data, int search_number)
{
	ArrayList allindexof = new ArrayList();
	for(int i=0;i<data.Length;i++)
		if(data[i] == search_number) allindexof.Add(i);
	
	return allindexof;
}

これで表示部分も foreach を使って記述できます。実行するには System.Collections名前空間を using しておく必要があります。

ArrayListクラスは動的にメモリ領域を確保する機能を持っており、大変高機能です。実際にプログラミングをする際には大いに活用したい機能ですが、アルゴリズムを学ぶ際は裏技であると考えて使わないことにします。

線形探索の役割

探索アルゴリズムは配列の探索と文字列の探索に大きくわかれています。配列の探索であればこのアルゴリズム入門で紹介する3つの方法以外にはほとんど定番といえるものはありません。

線形探索はアルゴリズムといえないほど単純ですが、実際にはよく使われます。コンピュータは力技が得意なので、その他のアルゴリズムでも力技を用いることがしばしばあります。

線形探索は value の型が文字列であってもアルゴリズムをそのまま適用できます。特に速度を必要とする場合以外は、線形探索を用いても特に問題はありません。もっとも原始的ですが、その分もっとも万能な探索アルゴリズムです。