二分探索とその応用 ── 「ソート済み」を見たら反射的に

2026/04/26

二分探索とその応用 ── 「ソート済み」を見たら反射的に

扱う概念：二分探索の基本、境界値の扱い（lower_bound / upper_bound）、回転ソート配列、二分探索の一般化（条件の単調性）

二分探索パターン — lower_bound・回転配列・答えの空間探索

この章で何ができるようになるか：「ソート済みデータに対して O(log n) で答えを出す」パターンを体系的に身につけ、二分探索を「配列の検索」だけでなく「答えの空間を絞り込む」テクニックとして使えるようになる。

基本の二分探索

def binary_search(arr: list[int], target: int) -> int:
    """target のインデックスを返す。なければ -1"""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # オーバーフロー対策
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

よくあるバグ：

lo + hi のオーバーフロー → lo + (hi - lo) // 2 で回避
while lo < hi vs while lo <= hi の使い分け
lo = mid vs lo = mid + 1 の選択ミス → 無限ループ

lower_bound / upper_bound

「target 以上の最初の位置」「target より大きい最初の位置」を求める。

def lower_bound(arr: list[int], target: int) -> int:
    """target 以上の最初のインデックスを返す（挿入位置）"""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

def upper_bound(arr: list[int], target: int) -> int:
    """target より大きい最初のインデックスを返す"""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 応用：target の出現回数
def count_occurrences(arr, target):
    return upper_bound(arr, target) - lower_bound(arr, target)

# arr = [1, 2, 2, 2, 3, 4]
# lower_bound(arr, 2) → 1（最初の2の位置）
# upper_bound(arr, 2) → 4（最後の2の次の位置）
# count = 4 - 1 = 3

Python の bisect モジュール：

import bisect

arr = [1, 2, 2, 2, 3, 4]
bisect.bisect_left(arr, 2)   # 1（= lower_bound）
bisect.bisect_right(arr, 2)  # 4（= upper_bound）
bisect.insort(arr, 2.5)      # ソート順を維持して挿入

回転ソート配列の探索

def search_rotated(nums: list[int], target: int) -> int:
    """
    [4, 5, 6, 7, 0, 1, 2] のような回転ソート配列で target を検索
    """
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid

        # 左半分がソート済みか判定
        if nums[lo] <= nums[mid]:
            # target が左半分の範囲内ならそちらへ
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            # 右半分がソート済み
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1

    return -1

二分探索の一般化：答えの空間を探索する

二分探索は「配列の中から要素を探す」だけではない。条件の単調性がある任意の問題に使える。

パターン：「最小の X で条件を満たすものを求めよ」

def binary_search_answer(lo: int, hi: int, condition) -> int:
    """
    condition(x) が False, False, ..., True, True, ... と変わる
    最初に True になる x を見つける
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

例1：船の最小積載量

def ship_within_days(weights: list[int], days: int) -> int:
    """weights を days 日以内に運ぶための最小の船の積載量"""

    def can_ship(capacity: int) -> bool:
        day_count, current_load = 1, 0
        for w in weights:
            if current_load + w > capacity:
                day_count += 1
                current_load = 0
            current_load += w
        return day_count <= days

    lo = max(weights)       # 最低でも最大の荷物は積める必要がある
    hi = sum(weights)       # 最大は全部1日で運ぶ場合
    return binary_search_answer(lo, hi, can_ship)

例2：平方根の近似

def sqrt_int(n: int) -> int:
    """n の平方根の整数部分を返す"""
    lo, hi = 0, n
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if mid * mid <= n < (mid + 1) * (mid + 1):
            return mid
        elif mid * mid > n:
            hi = mid - 1
        else:
            lo = mid + 1
    return lo

例3：行列のK番目に小さい要素

def kth_smallest_in_sorted_matrix(matrix: list[list[int]], k: int) -> int:
    """各行・各列がソートされた n×n 行列の k 番目に小さい要素"""
    n = len(matrix)

    def count_le(mid: int) -> int:
        """mid 以下の要素数を O(n) で数える"""
        count = 0
        row, col = n - 1, 0
        while row >= 0 and col < n:
            if matrix[row][col] <= mid:
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    lo, hi = matrix[0][0], matrix[n-1][n-1]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if count_le(mid) < k:
            lo = mid + 1
        else:
            hi = mid
    return lo

二分探索が使えるサイン

✅ 使えるパターン：
  - 「ソート済み配列から値を探す」
  - 「条件を満たす最小/最大の値を求める」（条件が単調）
  - 「答えの候補が単調に変化する」

❌ 使えないパターン：
  - ソートされていない・単調性がない
  - 候補が離散的に飛んでいる（ギャップがある）

まとめ

パターン	テンプレート	計算量
値の検索	`while lo <= hi`	O(log n)
lower_bound	`while lo < hi` + `hi = mid`	O(log n)
upper_bound	`while lo < hi` + `lo = mid + 1`	O(log n)
回転配列	左右どちらがソート済みか判定	O(log n)
答えの二分探索	`condition(mid)` で範囲を絞る	O(log(答え空間) × 判定コスト)