@blog.justoneplanet.info

集団が予め整列されている時の探索。

■実装

var a =  [0, 3, 6, 9, 12, 15, 18, 21, 24, 27];


var search = function(ary, elm){
    low  = 0;
    high = ary.length - 1;
    while(low <= high){
        var i = Math.floor((low + high) / 2);
        if(ary[i] === elm){
            return i;
        }
        else if(ary[i] > elm){
            high = i - 1;
        }
        else{
            low = i + 1;
        }
    }
    return -1;
};


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

■特性

• 電話帳や名簿など予め整列された集合に対して有用である
• 最良時にO(1)、平均と最悪時の計算コストはO(log n)となる