JavaScriptで二分探索(UpperBound, LowerBound)をしてみる

5379 ワード
データ構造 JavaScript JavaScript テキストリンク

LowerBound,UpperBoundとは

二分探索の一種のようなもの。

-lowerboundは、指定された要素以上の値が現れる最初の位置を返す
-upperboundは、指定された要素より大きい値が現れる最初の位置を返す

例

分かりにくいので具体例
前提として二分探索と同じくソート済みの配列に対して使います

[2, 4, 20, 22, 30, 34]

こんな配列があったします。
例えばlowerBound(15)で得られるのは「２」です。
他にはupperBound(15)で得られるのは「3」です。

boundっていう名前の通り境界の位置を返してくるイメージだと分かりやすいかもしれません。

コード

const lowerBound = (arr, n) => {
    let 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;
}

const upperBound = (arr, n) => {
    let 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;
}