@blog.justoneplanet.info

■実装

まぁ、簡単すぎるけど一応書いておく。

var n = 10;
var a = [];
for(var i = 0; i < n; i++){
    a[i] = Math.round(Math.random() * n);
}

var search = function(ary, elm){
    for(var i = 0; i < ary.length; i++){
        if(ary[i] === elm){
            return i;
        }
    }
    return -1;
};

console.log(a.toString());
console.log(search(a, 5));

■特性

• 整列していない要素の少ない配列に対して有効
• 殆どの場合で-1を返すような場合、違ったアルゴリズムを検討するべき
• 最良時は配列の先頭に要素がある場合で計算量はO(1)
• 最悪時は配列の最後尾に要素がある場合で計算量はO(n)
• 平均すると配列の中央まで探索することになり計算量はO(n)
• 探索が成功した場合に要素を先頭や最後尾に移動させることにより、複数回の探索時の性能をあげられる可能性がある