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

追記: さすがに雑だったので書き直しました。

www.pandanoir.info

lower_bound()とupper_bound()のJavaScriptによる実装がなかったので、ネットでlower bound関連の記事漁りつつ適当にテストしたプログラム載せておきます。

function lower_bound(arr, n) {
    var first = 0, last = arr.length - 1, middle;
    while (first <= last) {
        middle = 0 | (first + last) / 2;
        if (arr[middle] < n) first = middle + 1;
        else last = middle - 1;
    }
    return first;
};
function upper_bound(arr, n) {
    var first = 0, last = arr.length - 1, middle;
    while (first <= last) {
        middle = 0 | (first + last) / 2;
        if (arr[middle] <= n) first = middle + 1;
        else last = middle - 1;
    }
    return first;
};

簡単な仕様

lower_bound(Array, N)

返り値: Arrayの中でN以上となる最小値のインデックス。該当する値がない時はArrayの長さ。

例:

lower_bound([1, 3, 5], 0) === 0;
lower_bound([1, 3, 5], 2) === 1;
lower_bound([1, 3, 5], 3) === 1;
lower_bound([1, 3, 5], 6) === 3;

upper_bound(Array, N)

返り値: Arrayの中でNより大きい値のうち最小となる値のインデックス。該当する値がない時はArrayの長さ。

例:

upper_bound([1, 3, 5], 0) === 0;
upper_bound([1, 3, 5], 2) === 1;
upper_bound([1, 3, 5], 3) === 2;
upper_bound([1, 3, 5], 6) === 3;

よくある使い方

配列中のある値がいくつあるのか数えるあれですね。

console.log(upper_bound(array, n) - lower_bound(array, n));

一応これが通るようにテストしたのでこれで数え上げられることは保証します。まあエラー出ても文句は言わないでください。

通したテスト

テストかなり雑に書いたので自信ないです。まあ多分大丈夫でしょう。arrとして用意した配列は0以上1000未満の乱数1000個格納した配列です。長いので割愛しました。

var arr = [1,3,4,4,...,992,992,996,997];
var error = 0;
for (var i = 0; i < 1000; i++){
    var lo = lower_bound(arr, i), hi = upper_bound(arr, i);
    if (hi - lo > 0 && (i !== arr[lo] || arr[lo] !== arr[hi - 1] || arr[lo] === arr[hi])) {
            error++;
    }
    if (hi - lo === 0) {
        if (i >= arr[lower_bound(arr, i)] || i >= arr[upper_bound(arr, i)]) {
            error++;
        }
    }
}
console.log('error', error);