JavaScript リニアサーチとバイナリサーチ

JavaScriptで表す線形探索(リニアサーチ)と二分探索（バイナリサーチ）

#線形探索(リニアサーチ)
「先頭から順番に探す値が見つかるまで探す方法」
配列を直線的（リニア）に探すので「リニアサーチ」と呼ばれる。
値をひとつひとつ調べていくので、データが大量になると時間がかかってしまう。

手順
1 先頭から末尾まで順番に値を調べる。
2 「調べた値」と「探す値」が同じならサーチ終了。

JavaScript

script.js

//検索する配列データ
var a = [1,3,10,2,8];

//検索する値
var searchValue = 2;

//「調べた値」と「探す値」が一致したとき、indexを保存する変数。
//初期値はエラー(-1)に設定
var index = -1;

//繰り返し処理　
for(var i=0; i< a.length;i++){
    //条件分岐 「調べた値」と「探す値」が一致したとにきにindexを保存して処理終了
    if(a[i] == searchValue){
        index = i;
        break;
    }
}
//検索結果を表示する。(-1の場合は値がなかった)
console.log(a[index]);

#二分探索(バイナリサーチ)
「調べる範囲を半分に絞りながら探す方法」
範囲を「二つ(バイナリ)に分けて」探すので「バイナリサーチ」と呼ばれる。
データがばらばらに並んでいると規則性がないので、あらかじめデータを順番に並べておく必要がある。

手順
前提 値が順番に並んでいる
1 調べる範囲の左端と右端を決める
2 真ん中の位置を求める
(真ん中の値が「探す値」と一致したら処理終了)
3 真ん中の値が「探す値」より小さければ左端を移動する
(左側にはもっと小さい値しかないので、調べる必要がない)
4 真ん中の値が「探す値」より大きければ右端を移動する
(右側にはもっと大きい値しかないので、調べる必要がない)
5 調べる左端と右端の間にデータがある間は1~4の処理を繰り返す

JavaScript

script.js

//検索するソート済みの配列データ
var a = [1,2,4,5,10];

//探す値
var searchValue = 1;

//
//「調べた値」と「探す値」が一致したとき、indexを保存する変数。
//初期値はエラー(-1)に設定
var index = -1;

//調べる左端を表す添字(index)
var left = 0;

//調べる右端を表す添字(index)
var right = a.length-1;

//左端と右端にデータがある間は処理を繰り返す
while(left <= right){

    //左右の真ん中を表す添字(index)
    middle =Math.floor((left +right)/2);

    //真ん中の値と探す値を比較する
    if(a[middle]==searchValue){
        //一致した場合、変数に入れて処理終了
        index = middle;
        break;
    }else if(a[middle]<searchValue){
        //探す値より小さい場合、左側にはもっと小さい値しかないので左端の値を真ん中の値の右に移動する
        left = middle +1;
    }else{
        //探す値より大きい場合、右側にはもっと大きい値しかないので右端の値を真ん中の値の左に移動する
        right = middle -1;
    }
}

//検索結果を表示する。(-1の場合は値がなかった)
console.log(a[index]);

補足
配列の真ん中の値は左端と右端を足して2で割ると求めることができるが、奇数の場合少数点以下を切り捨てる処理が必要になる。
JavaScriptではMath.floor()で少数点切り捨てになる。