아래 코드는 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;
}