【Underscore.js】_.sortedIndexを読んだ

jashkenas/underscoreの_.sortedIndexを読んだ。

概要

_.sortedIndex(list, value, [iteratee], [context]) 

ソートされているlistに対して、valueがどの位置に入るかを返す。

_.sortedIndex([10, 20, 30, 40, 50], 35); // 3

ソースコード

_.sortedIndex = function(array, obj, iteratee, context) {
    iteratee = cb(iteratee, context, 1);
    var value = iteratee(obj);
    var low = 0, high = getLength(array);
    while (low < high) {
      var mid = Math.floor((low + high) / 2);
      if (iteratee(array[mid]) < value) low = mid + 1; else high = mid;
    }
    return low;
  };

while文の中で二分探索をしている。

参考

jashkenas/underscore