Median of Two Sorted Arrays

📋 アルゴリズム概要

2つのソート済み配列 nums1 と nums2 が与えられたとき、それらをマージした際の中央値を求める問題です。 要件として O(log(m+n)) の時間計算量が求められています。

戦略：短い配列に対して二分探索を行い、両配列を「左半分」と「右半分」に分割するパーティション点を探します。 正しいパーティションでは、左半分の最大値 ≤ 右半分の最小値が成立します。

🎯 ステップバイステップ解説

💻 Python実装

from __future__ import annotations

from typing import Final, List


class Solution:
    """
    Median of Two Sorted Arrays
    - Time:  O(log(min(m, n)))
    - Space: O(1)
    速度・メモリ最適化版（二分探索パーティション法）
    """

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        """
        2つのソート済み配列の中央値を計算する。

        Args:
            nums1: 非減少順の整数配列（長さ 0..1000）
            nums2: 非減少順の整数配列（長さ 0..1000）

        Returns:
            中央値（偶数長の場合は中央2要素の平均）
        """
        # --- 短い配列をAにする（探索範囲を最小化） ---
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        A: List[int] = nums1
        B: List[int] = nums2
        a_len: int = len(A)
        b_len: int = len(B)

        # 総数と奇偶を事前計算（ループ内の分岐削減）
        total: int = a_len + b_len
        total_is_odd: bool = (total & 1) == 1
        half: int = (total + 1) >> 1  # 左側に含める要素数

        # 整数センチネル（制約±1e6を超える値）
        NEG: Final[int] = -10_000_007
        POS: Final[int] = +10_000_007

        lo: int = 0
        hi: int = a_len

        # --- 二分探索によるパーティション点の探索 ---
        while lo <= hi:
            i: int = (lo + hi) >> 1  # Aの左パート長
            j: int = half - i         # Bの左パート長

            # 境界値の取得（範囲外はセンチネル）
            a_left: int = NEG if i == 0 else A[i - 1]
            a_right: int = POS if i == a_len else A[i]
            b_left: int = NEG if j == 0 else B[j - 1]
            b_right: int = POS if j == b_len else B[j]

            # パーティション条件のチェック
            if a_left <= b_right and b_left <= a_right:
                # 正しいパーティションを発見
                if total_is_odd:
                    # 奇数長：左側の最大値が中央値
                    return float(a_left if a_left > b_left else b_left)
                # 偶数長：左側最大と右側最小の平均
                left_max: int = a_left if a_left > b_left else b_left
                right_min: int = a_right if a_right < b_right else b_right
                return (left_max + right_min) * 0.5

            # パーティション調整
            if a_left > b_right:
                # Aの左が大きすぎる → Aの左パートを減らす
                hi = i - 1
            else:
                # Aの右が大きすぎる → Aの左パートを増やす
                lo = i + 1

        # 入力が正しければここには到達しない
        return 0.0

📊 視覚的図解・フローチャート

フローの説明：
1. 短い配列をAにする（探索範囲を最小化）
2. 中央値を求めるための半分の長さ（half）を計算
3. 二分探索でパーティション点iを探索
4. パーティション点jを自動的に決定（j = half - i）
5. 境界値を取得してパーティション条件をチェック
6. 条件を満たせば中央値を返す、満たさなければiを調整して再探索

⚡ 計算量説明