値の探索(整数) - 【ゆるゆるプログラミング】

2020/03/23 公開

・値の探索(整数)

ここでは、リニアサーチ（線形探索法）を使って配列の値を探索する方法を説明します。

この方法は単純で、配列の最初の値から順番に、検索する値と同じ値を探していきます。同じ値が見つかったら処理を終了します。

以下の図は、要素数が７個の任意の整数が格納されている配列です。右方向の矢印は値を探す順番を表しています。

例えば、６７を見つける場合、配列の添え字０から６まで順番に値が６７を探していきます。

この例では、配列の５番目の値（添え字４）が６７です。

この方法は単純な方法なので、プログラミングは簡単です。ただし、配列に格納されている値を順番に探索していくため、要素数が多いと検索するのに時間がかかるというデメリットがあります。要素数が少ない配列の場合は、この方法は実用的です。

以下は、リニアサーチ（線形探索法）のJava ソースコード例です。

LinearSearchInt.java　←　クリックしてダウンロードページに移動

001:    public class LinearSearchInt {
002:    	// 指定した値を配列から検索
003:    	//   検索対象の値を格納した配列ary
004:    	//   検索する値をseekval
005:    	static int linearsearch( int[] ary, int seekval )
006:    	{
007:    		// forで順番に値を比較する
008:    		for ( int i = 0; i < ary.length; i++ )
009:    		{
010:    			// 一致する値が見つかった場合、その添え字を戻す
011:    			if ( ary[ i ] == seekval )
012:    				return i;
013:    		}
014:    
015:    		// seekvalと一致する値が無い場合、-1を戻す
016:    		return -1;
017:    	}
018:    
019:    
020:    	// メイン
021:    	public static void main( String[] args ) {
022:    		// 配列に任意の値を格納
023:    		int[] ary = { 84, 17, 33, 2, 67, 55, 49 };
024:    
025:    		// 値の検索
026:    		int ans, seekval;
027:    
028:    		// 67を検索
029:    		seekval = 67;
030:    		ans = linearsearch( ary, seekval );
031:    		if ( 0 > ans )
032:    			System.out.println( seekval + "は配列に存在しません！" );
033:    		else
034:    			System.out.println( seekval + "はary[" + ans + "]にあります" );
035:    
036:    		// 5を検索
037:    		seekval = 5;
038:    		ans = linearsearch( ary, seekval );
039:    		if ( 0 > ans )
040:    			System.out.println( seekval + "は配列に存在しません！" );
041:    		else
042:    			System.out.println( seekval + "はary[" + ans + "]にあります" );
043:    	}
044:    }

LinearSearchIntの出力結果

67は配列のary[4]にあります
5は配列に存在しません！

検索する値が見つかった場合、配列の添え字（配列の位置）を出力しています。

それでは、ここからソースコードを解説していきます。

001:    public class LinearSearchInt {

クラス名を、LinearSearchとしています。

002:    	// 指定した値を配列から検索
003:    	//   検索対象の値を格納した配列ary
004:    	//   検索する値をseekval
005:    	static int linearsearch( int[] ary, int seekval )
006:    	{

リニアサーチ（線形探索法）を行うlinearsearchメソッドです。int型の配列aryと検索する値seekvalを渡して配列の添え字を戻します。seekvalと同じ値が配列の中に無い場合は-1を戻します。

007:    		// forで順番に値を比較する
008:    		for ( int i = 0; i < ary.length; i++ )
009:    		{
010:    			// 一致する値が見つかった場合、その添え字を戻す
011:    			if ( ary[ i ] == seekval )
012:    				return i;
013:    		}

for文を使って、配列の値をary[0]からary[ary.length]まで順番にseekvalと同じ値かを判定し、同じ値であれば添え字の変数iの値を戻します。同じ値が見つからない場合はforループを抜けて-1を戻します。

020:    	// メイン
021:    	public static void main( String[] args ) {

このmainメソッドからプログラムを実行します。

022:    		// 配列に任意の値を格納
023:    		int[] ary = { 84, 17, 33, 2, 67, 55, 49 };

int型の配列を作成し、７個の任意の値を代入しています。

025:    		// 値の検索
026:    		int ans, seekval;

検索した添え字を格納するint型の変数ans、検索する値を格納するint型の変数seekvalを宣言しています。

028:    		// 67を検索
029:    		seekval = 67;
030:    		ans = linearsearch( ary, seekval );
031:    		if ( 0 > ans )
032:    			System.out.println( seekval + "は配列に存在しません！" );
033:    		else
034:    			System.out.println( seekval + "はary[" + ans + "]にあります" );

linearsearchメソッドに検索する値seekval=67を渡して、値が67の配列の添え字を変数ansに代入しています。配列の中に67が無い場合、変数ansが-1になります。

036:    		// 5を検索
037:    		seekval = 5;
038:    		ans = linearsearch( ary, seekval );
039:    		if ( 0 > ans )
040:    			System.out.println( seekval + "は配列に存在しません！" );
041:    		else
042:    			System.out.println( seekval + "はary[" + ans + "]にあります" );

linearsearchメソッドに検索する値seekval=5を渡して、値が5の配列の添え字を変数ansに代入しています。配列の中に67が無い場合、変数ansが-1になります。

以上です。

■関連コンテンツ

配列のソート	配列を昇順・降順に並び替える方法を解説
Javaの配列	同じ型の変数をまとめた配列について解説
変数値の交換	２つの変数値を交換する方法を解説

	for文繰り返し処理に使用するfor文をJavaのソースコードを使って説明しています。
	if文条件による処理の分岐に使用するif文について解説
	Javaの変数変数は、プログラムの中で値を入れておく入れ物のようなものです。