集団が予め整列されている時の探索。
■実装
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)となる