Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

lower_boundとupper_boundをJavaScriptで実装してみた

http://www.cplusplus.com/reference/algorithm/lower_bound/

ここの仕様を満たすように実装していきます。

lower_bound()とupper_bound()をJavaScriptで実装してみたのリベンジ記事です。

仕様

要約するとこの辺を満たせばよさそうです。

  • [first, last)の範囲で探索
  • 範囲内で最初のval以上の値を指すイテレータを返す。ただし、JavaScriptでは表現不可なので添字を返すとする。
  • [first, last)の値がすべてval未満の時はlastを指すイテレータを返す。ただし、これはJavaScriptで表現不可なので配列の長さを返すとする。
  • compは今回パスで。てか「STLとほぼ同じコード書くとこうだよ!」と言って書いてあるコードにすら存在してないし

線形探索による実装

まずは線形探索でlower_boundを実装します。val以上の値が出てきたらその値を返すというだけです。コードから明らかに仕様を満たしているとわかります。

const lower_bound = (arr, val, first = 0, last = arr.length) => {
    for (; first < last; first++) {
        if (arr[first] < val)
            continue;
        return first;
    }
    return first;
}

二分探索を応用した実装する

とりあえず線形探索では実装できました。あとはこれを崩さないように気をつけつつ二分探索に落とし込みます。

方針としては、「val未満の位置」「val以上の位置」を保持しておき、その2つが隣接したらval以上の位置を返して終了します。

ここから少しテクニカルな話になります。まず、与えられる配列は3ケースが考えられます。

  1. val未満の要素が存在しない
  2. val未満の要素が存在する
  3. val未満の要素のみ

「val未満の位置」の初期値を配列の先頭にしてしまうと、(1)のケースを満たせなくなってしまいます。そこで、val未満の位置をひとつ外側にずらすことで(1)に対応させます。同様に、val以上の位置の初期値も配列の範囲外に設定します。

このように、はじめのval未満の位置、val以上の位置を設定したら、あとはただの二分探索です。

const lower_bound = (arr, val, first = 0, last = arr.length) => {
    first -= 1; // はじめの位置をひとつずらす
    // 探索範囲が[first, last)のため、lastはずらさなくていい。
    const mid = first + Math.floor((last - first) / 2);
    if (last - first == 1 )
        // 「val未満の位置」と「val以上の位置」が隣接した
        return last;
    if (arr[mid] < val)
        return lower_bound(arr, val, mid, last);
    return lower_bound(arr, val, first, mid);
}

この実装は上の議論の通りになっています。

再帰関数をループに書き直す

最後に再帰関数をループに落とし込めば完成です。二分探索なのでスタックオーバーフローすることはほぼありえませんが、パフォーマンス考えるとやはりループに展開したほうが得です。

const lower_bound = (arr, val, first = 0, last = arr.length) => {
    first -= 1; // 一番端の位置からさらにずらす
    while (last - first > 1) {
        const mid = first + Math.floor((last - first) / 2);
        if (arr[mid] < val)
            first = mid;
        else
            last = mid;
    }
    return last;
}

これで本当に完成です。

ちょっと高速化する

const lower_bound = (arr, val, first = 0, last = arr.length) => {
    first -= 1;
    for (let m; last - first > 1;) {
        if (arr[m = first + (0 | (last - first) / 2)] < val)
            first = m;
        else
            last = m;
    }
    return last;
}

Closure Compilerによるさらなる圧縮後

const lower_bound=(d,e,b,a)=>{a=void 0===a?d.length:a;b=(void 0===b?0:b)-1;for(let c;1<a-b;)d[c=b+(0|(a-b)/2)]<e?b=c:a=c;return a};

upper_boundを実装する

ここまで分かれば簡単にupper_boundも実装できます。

const upper_bound = (arr, val, first = 0, last = arr.length) => {
    first -= 1;
    while (last - first > 1) {
        const mid = first - Math.floor((last - first) / 2);
        if (arr[mid] <= val) // ココを直すだけ
            first = mid;
        else
            last = mid;
    }
    return last;
}

圧縮後

const lower_bound=(d,e,b,a)=>{a=void 0===a?d.length:a;b=(void 0===b?0:b)-1;for(let c;1<a-b;)d[c=b+(0|(a-b)/2)]<=e?b=c:a=c;return a};