エンジニアなら知っておくべき探索アルゴリズムの種類

こんにちは、しょうぞうです。

今回は、アルゴリズムに関して記事を書いていきたいと思います。

アルゴリズムには種類がいくつかあって代表的なアルゴリズムをそれぞれ紹介していきたいとおもいます。

アルゴリズムとは

アルゴリズムとは、「どのように処理をさせると機能を満たすだろうか」や「どのような手順を踏めばより効率的になるだろうか」などをもとに考えられた手順のことを意味します。

アルゴリズムさえ考えれば、あとはそれをプログラミング言語で置き換えて書いていけばいいので、最も重要な部分だと考えられています。

一連の流れを図で表したものをフローチャートで書いたりします。

アルゴリズムの中でも代表的なものを紹介していきたいと思います。

線形探索法

線形探索法とは、先頭から順番に探す値を見つかるまで探すアルゴリズムです。

データが見つかるか配列の数の範囲を超えるまでループで検索し続けるというものです。

コードで書くと以下のようになります。


	public class Algorithm {

	public static void main(String[] args) {

	int x = 10;

	int[] array = {7,4,2,8,10,9,1,5,3,6};

	String search = "値はありません";

	for(int i = 1; i < array.length; i ++) {

	if(x == array[i]) {
	search = "値はありました";
	}

	}

	System.out.println(search);



	}

	}

view raw linear search hosted with ❤ by GitHub

線形探索法では、「目的のデータかどうか」と「配列の数の範囲を超えたかどうか」の２つの判定が毎回行われるため処理が効率的でないとされています。

それを解消したのが番兵法というものです

番兵法というのは、配列の最後に探そうとしている目的の値を追加することで配列の中に目的の値が必ずある状態を作り、「配列の数の範囲を超えたかどうか」という判定を省略するというものです。

コードで書くと以下のようになります。

	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.List;



	public class Sentinel {

	public static void main(String[] args) {

	Integer x = 25;

	Integer[] array = {7,4,2,8,10,9,1,5,3,6};
	//配列をArrayListに変換
	List<Integer> newArray = new ArrayList<>(Arrays.asList(array));

	newArray.add(x);

	String search = "値はあります";

	Integer i = 0;

	while (x != newArray.get(i)) {
	i++ ;
	}

	//元々の配列の長さよりiの数が大きい場合は存在していない
	if(i >= array.length) {
	search = "値はありませんでした";
	System.out.println(search);
	}else {
	System.out.println(search);
	}

	}

	}

view raw Sentinel hosted with ❤ by GitHub

二分探索法とは、あらかじめ探索対象のデータ群が「昇順にならんでいる」「降順に並んでいる」というようにソートされていて規則性を持っている場合により効率的な方法で探索できる方法です。

やり方としては、データの集合をざっくり2つに分けながら対象を絞り込んでいくといった形になります。

コードで表すと以下のような感じです。


	public class BinarySearch {

	public static void main(String[] args) {
	int[] array = { 1, 4, 5, 7, 9, 10, 16 };

	int low = 0;
	int high = array.length - 1;

	int x = 7;
	int number = -1;

	while (low <= high) {

	int mid = (low + high) / 2;

	if (array[mid] == x) {
	number = mid;
	break;
	} else if (array[mid] < x) {
	low = mid + 1;
	} else {
	high = mid - 1;
	}

	}

	if(number < 0) {
	System.out.println("値はありませんでした");
	}else {
	System.out.println("値は" + number + "番目です。");
	}

	}

	}