アルゴリズム 線形探索

ある意味単純。

頭から探すだけ。

コピペ

線形探索

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つの線形探索アルゴリズムを書いてみました。

• IndexOf() = value が最初に見つかった index を求める
• LastIndexOf() = value が最後に見つかった index を求める
• AllIndexOf() = value が見つかった index をすべて求める