Binary search と各バリエーション: lower bound、回転配列、答え探索

1. 概要

Binary search はソート済みデータに対する検索アルゴリズムで、時間計算量は O(log n) です。考え方は非常にシンプルですが、実装は誤りやすいです：無限ループ、オフバイワンエラー (off-by-one)、mid の計算時のオーバーフロー。

この記事は基本的な実装から始まり、重複する要素の最初/最後の位置を見つけたり、出現回数をカウントしたり、回転配列で探索したり、答え探索のBinary searchなどの一般的なバリエーションまで進みます。読み終わった後、エラーが少ない実装フレームワークと検証用テストが手に入ります。

2. Binary search の基本

昇順にソートされた商品価格の配列があり、特定の価格位置を見つける必要があると仮定します：

public final class PriceSearch {

    public static int search(int[] prices, int target) {
        int lo = 0;
        int hi = prices.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (prices[mid] == target) {
                return mid;
            }
            if (prices[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] prices = {100, 150, 200, 350, 500};
        System.out.println(search(prices, 350));
        System.out.println(search(prices, 300));
    }
}

説明：

• lo と hi は閉区間 [lo, hi] を形成します。これは target が存在するはずの領域です。
• 条件 lo <= hi は、区間に少なくとも1つの要素が含まれている限り、ループが続くことを意味します。
• mid = lo + (hi - lo) / 2 はオーバーフローを回避します。(lo + hi) / 2 という書き方は、lo + hi が Integer.MAX_VALUE を超えるとオーバーフローします。同等の方法は (lo + hi) >>> 1 です。
• 各ステップで、mid を区間から除外します（mid + 1 または mid - 1）。したがって、区間は常に縮小し、ループは確実に終了します。

結果：

3
-1

このバージョンは、配列に重複要素がなく、単に「存在するかしないか」を知りたい場合に十分です。重複がある場合、重複グループ内の任意の位置が返されます。通常、これは望ましくありません。

3. Lower bound と Upper bound

最も重要な2つのバリエーションは：

• lower bound: a[i] >= target である最初のインデックス。
• upper bound: a[i] > target である最初のインデックス。

両者は常に [0, n] の範囲内のインデックスを返します。target がない場合でも同様です。このインデックスは、配列をソート状態に保つための挿入位置です。

public final class Bounds {

    public static int lowerBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;              // 半開区間 [lo, hi)
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static int upperBound(int[] a, int target) {
        int lo = 0;
        int hi = a.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

基本版との違い：

• 半開区間 [lo, hi) を使用します。そのため、hi は a.length で初期化され、ループ条件は lo < hi です。
• a[mid] が「十分に大きい」という条件を満たす場合、mid - 1 ではなく hi = mid を割り当てます。なぜなら mid はまだ答えの候補だからです。
• 2つの関数は < と <= の記号のみ異なります。

重複要素を含む配列で試してみます：

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Bounds.lowerBound(prices, 200)); // 1
System.out.println(Bounds.upperBound(prices, 200)); // 4
System.out.println(Bounds.lowerBound(prices, 300)); // 4
System.out.println(Bounds.lowerBound(prices, 900)); // 6

1
4
4
6

300 の場合、結果 4 は、300 を挿入すると 350 の前に来ることを意味します。900 の場合、結果が n と等しい場合、すべての要素より小さいことを意味します。

3.1. 最初の位置、最後の位置、出現回数

上の2つの関数から、次のような身近な問題をすぐに導き出すことができます：

public static int firstIndexOf(int[] a, int target) {
    int i = Bounds.lowerBound(a, target);
    return (i < a.length && a[i] == target) ? i : -1;
}

public static int lastIndexOf(int[] a, int target) {
    int i = Bounds.upperBound(a, target) - 1;
    return (i >= 0 && a[i] == target) ? i : -1;
}

public static int count(int[] a, int target) {
    return Bounds.upperBound(a, target) - Bounds.lowerBound(a, target);
}

上記の prices と target = 200 で、firstIndexOf = 1、lastIndexOf = 3、count = 3 が得られます。重要な点：a[i] を読む前に、常に境界チェック i < a.length（または i >= 0）を行います。

3.2. 範囲内の要素数をカウント

実際の応用例は、価値が [min, max] の範囲内の注文数をカウントすることです：

public static int countInRange(int[] sortedTotals, int min, int max) {
    return Bounds.upperBound(sortedTotals, max) - Bounds.lowerBound(sortedTotals, min);
}

{100, 200, 200, 200, 350, 500} と範囲 [150, 400] では、結果は 6 - ... ですか？計算してみます：upperBound(400) = 5、lowerBound(150) = 1、したがって結果は 4 です。各クエリは O(log n) のみで済み、配列全体をスキャンする必要はありません。

4. 回転配列の検索

回転配列は、ソート済み配列を1つの点で「切断」し、2つの半分を入れ替えたもので、例えば {40, 50, 60, 10, 20, 30} のようになります。この配列は全体では単調増加していませんが、mid の周りの少なくとも一方の半分は順序が保たれています。このことを利用して、どちら方向に進むかを判断します：

public static int searchRotated(int[] a, int target) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) {
            return mid;
        }
        if (a[lo] <= a[mid]) {                 // 左側が順序を保っている
            if (a[lo] <= target && target < a[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {                               // 右側が順序を保っている
            if (a[mid] < target && target <= a[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return -1;
}

説明：

• a[lo] <= a[mid] は、セグメント [lo, mid] が単調増加していることを示しています。target がこのセグメントの値の範囲内にある場合、左側に縮小します。そうでない場合は右側に進みます。
• 残りの場合、セグメント [mid, hi] は単調増加していて、対称的に推論します。

System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 20));
System.out.println(searchRotated(new int[]{40, 50, 60, 10, 20, 30}, 45));

4
-1

注意： この実装は、配列に重複要素がないことを前提としています。{2, 2, 2, 3, 2} のような配列では、条件 a[lo] <= a[mid] は、どちら半分が順序を保っているのかを区別できなくなります。この場合、a[lo] == a[mid] の場合を lo を1単位増やすことで別途処理する必要があり、最悪時間計算量は O(n) になります。

5. 答え探索による Binary search

これは最も強力なバリエーションです。配列内を検索するのではなく、条件を満たす最小の値を見つけます。適用できる唯一の条件は、述語が単調性を持つことです。x が条件を満たす場合、x より大きいすべての値も条件を満たします。言い換えると、結果のシーケンスは false, false, ..., true, true の形になります。

一般的な関数を書きます：

import java.util.function.LongPredicate;

public final class AnswerSearch {

    /** [lo, hi] の中で ok が true を返す最小の値。ok(hi) == true と仮定。 */
    public static long firstTrue(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

この関数は lowerBound と同じ構造を持っています。実際、lowerBound は述語 a[i] >= target を持つ特殊ケースに過ぎません。

実際の問題に適用します。倉庫には決まった順序の荷物リストがあり、maxDays 日以内にすべて配送する必要があります。毎日、トラックは連続した荷物を運び、総重量がトラックの最大積載量を超えてはいけません。最小限の積載量はいくらですか？

import java.util.Arrays;

public final class ShippingPlanner {

    public static long minCapacity(int[] weights, int maxDays) {
        long lo = Arrays.stream(weights).max().orElse(0);
        long hi = Arrays.stream(weights).asLongStream().sum();
        return AnswerSearch.firstTrue(lo, hi, cap -> canShip(weights, maxDays, cap));
    }

    static boolean canShip(int[] weights, int maxDays, long capacity) {
        int days = 1;
        long load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                days++;
                load = 0;
            }
            load += w;
        }
        return days <= maxDays;
    }

    public static void main(String[] args) {
        System.out.println(minCapacity(new int[]{3, 2, 2, 4, 1, 4}, 3));
    }
}

説明：

• lo は最も重い荷物です。トラックは少なくともどの荷物でも運べる必要があります。hi は総重量です。その場合、必要な日数は1日だけです。したがって ok(hi) は必ず真です。
• canShip は貪欲法をシミュレートします。トラックに荷物を積み込み、超過したら新しい日に進みます。積載量が大きいほど必要な日数は少なくなるため、述語は単調性を持ちます。
• 総コストは O(n · log(sum)) で、各積載量を試すのではなく。

6

積載量 6 の場合、配送スケジュールは [3, 2]、[2, 4]、[1, 4] で、正確に3日です。積載量 5 の場合、4日必要なため、5 は不合格です。

このテンプレートを使用して、多くの他の問題を解くことができます。バッチ処理に必要な最小スレッド数、最小レート制限、ある数の整数平方根など。

6. Java の標準ライブラリを使用する

Java には Arrays.binarySearch と Collections.binarySearch があります。戻り値の意味をよく理解する必要があります：

int[] prices = {100, 200, 200, 200, 350, 500};
System.out.println(Arrays.binarySearch(prices, 350));
System.out.println(Arrays.binarySearch(prices, 300));

4
-5

• 見つかった場合、関数は要素のインデックスを返します。
• 見つからない場合、関数は -(insertionPoint) - 1 を返します。ここで挿入位置は 4 なので、結果は -5 です。挿入位置を取り戻すには、-(result) - 1 を計算します。
• 重複要素がある場合、ドキュメントは重複グループ内のどの位置が返されるかを保証していません。最初または最後の位置が必要な場合は、自分で書いた lowerBound/upperBound を使用してください。

オブジェクトのリストの場合、ソート順序に対応する Comparator を渡します：

record Order(String id, long total) {}

List<Order> orders = List.of(
        new Order("A1", 120), new Order("B7", 300), new Order("C3", 450));
int idx = Collections.binarySearch(
        orders, new Order("?", 300), Comparator.comparingLong(Order::total));
System.out.println(idx); // 1

注意： LinkedList に対する Collections.binarySearch は O(log n) には及びません。インデックスアクセスに O(n) かかるからです。ArrayList または配列を使用してください。

7. テスト

JUnit 5 と AssertJ のdependencyを追加します。プロジェクトが spring-boot-starter-test を使用している場合、両方は既に含まれています。

<dependency>
    <groupId>org.junit.jupiter</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>5.11.0</version>
    <scope>test</scope>
</dependency>
<dependency>
    <groupId>org.assertj</groupId>
    <artifactId>assertj-core</artifactId>
    <version>3.26.3</version>
    <scope>test</scope>
</dependency>

境界ケースのテストを書きます。ここが binary search が最も壊れやすい場所です：

import org.junit.jupiter.api.Test;
import java.util.Random;
import java.util.stream.IntStream;
import static org.assertj.core.api.Assertions.assertThat;

class BoundsTest {

    private final int[] prices = {100, 200, 200, 200, 350, 500};

    @Test
    void lowerAndUpperBoundHandleDuplicates() {
        assertThat(Bounds.lowerBound(prices, 200)).isEqualTo(1);
        assertThat(Bounds.upperBound(prices, 200)).isEqualTo(4);
    }

    @Test
    void boundsReturnInsertionPointAtEdges() {
        assertThat(Bounds.lowerBound(prices, 50)).isZero();
        assertThat(Bounds.lowerBound(prices, 900)).isEqualTo(prices.length);
        assertThat(Bounds.lowerBound(new int[0], 1)).isZero();
    }

    @Test
    void lowerBoundMatchesLinearScan() {
        Random random = new Random(42);
        for (int round = 0; round < 1_000; round++) {
            int[] a = random.ints(random.nextInt(20), 0, 10).sorted().toArray();
            int target = random.nextInt(12) - 1;
            int expected = (int) IntStream.of(a).filter(x -> x < target).count();
            assertThat(Bounds.lowerBound(a, target)).isEqualTo(expected);
        }
    }

    @Test
    void minCapacityFindsSmallestFeasibleValue() {
        int[] weights = {3, 2, 2, 4, 1, 4};
        assertThat(ShippingPlanner.minCapacity(weights, 3)).isEqualTo(6);
        assertThat(ShippingPlanner.canShip(weights, 3, 5)).isFalse();
    }
}

lowerBoundMatchesLinearScan テストは、1,000個のランダム配列（空の配列を含む）で線形スキャン方式と比較します。このタイプの比較テストは、手書きの例よりもオフバイワンエラーをはるかに良く検出します。

8. 一般的なエラーと Binary search を使うべきでない場合

一般的なエラー：

• 2つの区間規約を混合する。 hi = n（半開）で初期化しますが、while (lo <= hi) でループし、hi = mid - 1 を割り当てます。その結果、配列外を読むことになります。1つの規約を選び、一貫性を保ってください。
• 無限ループ。 lo = mid を mid = (lo + hi) / 2 と一緒に書く場合、hi = lo + 1 の場合 mid == lo となり、区間が縮小しません。本当に lo = mid が必要な場合は、切り上げます：mid = lo + (hi - lo + 1) / 2。
• mid の計算時または答え探索の binary search で合計を計算する際のオーバーフロー。大きくなる可能性のある値には long を使用してください。
• 述語が単調でない。 Binary search は依然として数値を返しますが、その数値は無意味です。適用する前に単調性を証明してください。

いつ binary search を使うべきでないか：

• データがソートされておらず、数回だけ検索する場合。ソートは O(n log n) かかりますが、線形検索は O(n) だけです。
• 多くの検索で単に「存在するかどうか」だけを確認する必要があります。この場合、HashSet は平均 O(1) を提供します。
• データが絶えず変化し、頻繁に挿入と削除が必要な場合。配列をソート順に保つには、各挿入に O(n) かかります。ceilingKey、floorKey、higherKey を備えた TreeMap/TreeSet を検討してください。これらは lower bound と upper bound に相当します。
• 配列が非常に小さい、数十個の要素だけです。線形スキャンはキャッシュのおかげで通常同じか高速で、コードはより単純です。

9. まとめ

Binary search は「配列内の要素を見つける」だけではありません。半開区間 [lo, hi) で lower bound と upper bound を理解すれば、最初/最後の位置、要素のカウント、範囲内のカウントなどの問題が数行で解けます。回転配列には、どちら半分が順序を保っているかを判定するステップが追加されます。答え探索による binary search は、単調述語を持つすべての問題に技法を拡張します。

単一の区間規約を保ち、>>> または lo + (hi - lo) / 2 を使用してオーバーフローを避け、常に線形検索との比較テストを実施してください。これら3つの習慣は、binary search がまだ引き起こすことで有名なほぼすべてのエラーを排除します。