アルゴリズムを覚えたあとにすることは、覚えたアルゴリズムでプログラミングを作ることです。そうすることにより、プログラムの書き方のバリエーションが増え、プログラミング技術が向上すると思います。
そこで、今回はJavaScriptを用いて、探索アルゴリズムをプログラミングしていきます。「線形探索法(リニアサーチ)」、「二分探索法(バイナリサーチ)」を紹介していますので、アルゴリズムをプログラミングする際の参考にして頂ければ幸いです。
探索アルゴリズムとは
探索アルゴリズムとは、目的のデータを探し出すアルゴリズムのことです。本記事では、以下の2つの探索アルゴリズムをJavaScriptでプログラミングしていきます。
- 線形探索(リニアサーチ)
- 二分探索(バイナリサーチ)
線形探索(リニアサーチ)とは
配列を先頭から順番に調べて探す探索アルゴリズムです。単純なアルゴリズムではありますが、探したいデータが配列の後尾だった場合、配列の要素をすべて確認することになるため、探索速度は遅くなります。
プログラミング
線形探索で必要なアルゴリズムは以下となります。処理の繰り返しは「for文]」、条件分岐は「if文」で実装します。また、JavaScriptではプログラムを終了するメソッドはないため、アルゴリズムを関数とし、「return」をすることで、アルゴリズムの処理を終了させています。
なお、サンプルコードでは、data変数(目的のデータ)、array変数(探索範囲)を事前に定義して、作成しています。
- アルゴリズム
- 配列の数だけ処理を繰り返す
- 目的のデータと配列の要素が一致した場合は、処理を終了する
- JavaScript
- 配列の長さ => [配列].length
var data = 3; // 目的のデータ
var array = [1, 2, 3, 4, 5]; // 探索範囲
function linearSearch() {
// 配列の数だけ処理を繰り返す
for (var i = 0; i < array.length; i++) {
// 目的のデータと配列の要素が一致しているか判断
if (data == array[i]) {
alert('配列の' + i + '番目でデータを確認しました。');
return; // 処理を終了
}
}
alert('データが見つかりませんでした。');
}
linearSearch();
二分探索(バイナリサーチ)とは
ソート済みの配列において、探索する範囲を半分に絞りながら探索するアルゴリズムです。探索範囲がソートされていることが条件となりますが、線形探索より効率よく探索をするため、探索速度は速くなります。
プログラミング
二分探索で必要なアルゴリズムは以下となります。「探索範囲の先頭」、「探索範囲の後尾」、「探索範囲の中央値」を変数とし、1回の処理毎に変数の値を増減させて、探索範囲を変えていきます。
中央値を求める際、小数点の切り上げまたは切り下げを行い、整数値にする必要があります。サンプルコードでは「Math.floor」を使い、小数点の切り下げを実装しています。
- アルゴリズム
- 探索範囲の先頭が探索範囲の後尾を上回るまで処理を繰り返す
- 探索範囲の中央値を求める
- 中央値と目的のデータが一致した場合は、処理を終了する
- 中央値が目的のデータより小さい場合は、「探索範囲の先頭を中央値 + 1」にする
- 中央値が目的のデータより大きい場合は、「探索範囲の後尾を「中央値 - 1」にする
- JavaScript
- ある条件に達するまで処理を継続 => while文
- 中央値を求め、小数点を切り捨てる => Math.floor(([探索範囲の先頭] + [探索範囲の後尾]) / 2)
var data = 7;
var array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
var head = 0; // 探索範囲の先頭
var tail = array.length; // 探索範囲の後尾
function binarySearch() {
// 探索範囲の先頭が探索範囲の後尾を上回るまで処理を繰り返す
while (head <= tail) {
var center = Math.floor((head + tail) / 2); // 探索範囲の中央値を計算
// 目的のデータと中央値を比較
if (array[center] == data) {
alert('配列の' + center + '番目でデータを確認しました。'); // 配列の3番目でデータを確認しました。
return;
} else if (array[center] < data) {
head = center + 1;
} else {
tail = center - 1;
}
}
alert('データが見つかりませんでした。');
}
binarySearch();
