BinarySearchで特定値の頻度を見つける方法

Intro

upperBoundとlowerBoundはバイナリ探索(binary search)に基づく二つの関数で、整列された配列またはリストから特定の値の位置を探すのに使われます。 この二つの関数の違いと役割は次のとおりです。

ここでBinary Searchをする前に、arrayは整列されていなければなりません。

LowerBound

lowerBound関数は、特定の値targetが配列またはリストに初めて現れる位置を探します。 もし、targetが配列に存在しない場合、targetより大きい値が初めて現れる位置を返します。 つまり、target以上の最初の位置を探します。

例:
並べ替えられた配列 arr = [1、2、4、4、5、6] があると仮定します。

lowerBound(arr, 4) は2 を返します。 (配列で4が初めて現れる位置)
lowerBound(arr, 3) は2 を返します。 （3は配列にないので、3より大きい値が初めて現れる位置）

UpperBound

upperBound関数は、特定の値targetが配列またはリストで初めて超過する位置を探します。 つまり、targetより大きい値が初めて現れる位置を返します。

例:
並べ替えられた配列 arr = [1、2、4、4、5、6] があると仮定します。

upperBound(arr, 4) は4 を返します。 (配列で4より大きい値が初めて現れる位置)
upperBound(arr, 3)は2を返します。 (3より大きい値が初めて現れる位置)

Difference

lowerBoundは配列でtargetが初めて現れる位置を返すか、targetが配列にない場合はtargetより大きい値が初めて現れる位置を返します。
upperBoundは配列でtargetより大きい値が初めて現れる位置を返します。
2つの関数の違いは次のような例で要約できます:

整列された配列 arr = [1、2、4、4、5、6] において target = 4 のとき:

lowerBound(arr, 4) は2 を返します。 (4が初めて現れる位置)
upperBound(arr, 4) は4 を返します。 (4より大きい値が初めて現れる位置)

import java.util.ArrayList;
import java.util.Collections;

public class Main {

    public static void main(String[] args) {
        ArrayList<Long> array = new ArrayList<>();
        // Array should be sorted!
        Collections.addAll(array, 1L, 2L, 4L, 4L, 5L, 6L);

        long target = 4;

        long lower = lowerBound(array, target);
        long upper = upperBound(array, target);

        System.out.println("Lower Bound of " + target + ": " + lower); // Should print 2 index
        System.out.println("Upper Bound of " + target + ": " + upper); // Should print 4 index
        System.out.println("Occurrences of " + target + ": " + (upper - lower)); // 2 counts 
    }

    public static long lowerBound(ArrayList<Long> array, long target) {
        int left = 0;
        int right = array.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (array.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    public static long upperBound(ArrayList<Long> array, long target) {
        int left = 0;
        int right = array.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (array.get(mid) <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

Summary

lowerBoundは、target値が最初に現れる位置を探します。
upperBoundは、target値より大きい値が最初に現れる位置を探します。

upperBound-lowerBoundは配列からtarget値の出現回数を計算します。

この結果は、並べ替えられた配列やリストから特定の値の頻度を計算するのに非常に役立ちます。 特に、特定の条件を満たす部分配列の和を見つける問題で活用できます。

個人的にはずっと忘れてしまう部分なので、この機会にまとめて作成してみます。 気になることがありましたら、コメントは歓迎します。