자바스크립트 이분탐색 알고리즘

아래 코드는 d2라이브러리의 bisect함수를 따온것이다.

d2라이브러리를 사용하는 것이 좋지만, 코딩테스트에서 d2라이브러리를 사용 못하는 상황에서 유용할것이다.

사용예

let arr=[1,2,3,4,5]


console.log(bysect.left(arr,3))//2

bysect코드

var bysect=bisector(ascending)

function bisector(f) {
    let delta = f;
    let compare = f;
  
    if (f.length === 1) {
      delta = (d, x) => f(d) - x;
      compare = ascendingComparator(f);
    }
  
    function left(a, x, lo, hi) {
      if (lo == null) lo = 0;
      if (hi == null) hi = a.length;
      while (lo < hi) {
        const mid = (lo + hi) >>> 1;
        if (compare(a[mid], x) < 0) lo = mid + 1;
        else hi = mid;
      }
      return lo;
    }
  
    function right(a, x, lo, hi) {
      if (lo == null) lo = 0;
      if (hi == null) hi = a.length;
      while (lo < hi) {
        const mid = (lo + hi) >>> 1;
        if (compare(a[mid], x) > 0) hi = mid;
        else lo = mid + 1;
      }
      return lo;
    }
  
    function center(a, x, lo, hi) {
      if (lo == null) lo = 0;
      if (hi == null) hi = a.length;
      const i = left(a, x, lo, hi - 1);
      return i > lo && delta(a[i - 1], x) > -delta(a[i], x) ? i - 1 : i;
    }
  
    return {left, center, right};
}
  


function ascending(a, b) {
    return a < b ? -1 : a > b ? 1 : a >= b ? 0 : NaN;
  }