[Algorithm] 淘汰與搜尋法

def find_fake_light(coins):
    if len(coins) == 1:
        return coins[0]
    k = len(coins) // 3
    left, right, rest = coins[:k], coins[k:2*k], coins[2*k:]
    ls, rs = sum(left), sum(right)
    if len(left) == len(right):
        if ls < rs:
            return find_fake_light(left)
        if ls > rs:
            return find_fake_light(right)
        return find_fake_light(rest)
    return find_fake_light(left + right + rest)

兩組各 4 枚硬幣：

• $S_1 = \{A, B, C, D\}$：恰有一枚偽幣，不知道偏輕或偏重
• $S_2 = \{T_1, T_2, T_3, T_4\}$：全是真幣，可作為參考

用天平兩次找出偽幣並判斷輕重。

資訊量檢查：$4 \times 2 = 8$ 種情況，$3^2 = 9$ 種結果路徑，$8 \leq 9$ 足夠。

第一次秤量 $W_1$：$\{A, B, C\}$ 對 $\{T_1, T_2, T_3\}$

第二次秤量 $W_2$：依 $W_1$ 結果決定

• $W_1$ 平衡 → $W_2$：$D$ 對 $T_1$。左重 → $D$ 重；左輕 → $D$ 輕。
• $W_1$ 左重 → $W_2$：$A$ 對 $B$。左重 → $A$ 重；右重 → $B$ 重；平衡 → $C$ 重。
• $W_1$ 左輕 → $W_2$：$A$ 對 $B$。左重 → $B$ 輕；左輕 → $A$ 輕；平衡 → $C$ 輕。

正確性驗證（8 種情況全覆蓋）：

關鍵技巧：用參考真幣壓住不確定性。第一次秤把「偽幣身分」與「偏向」耦合進同一個結果——平衡代表偽幣是 $D$（方向待查）、不平衡代表方向已定、只剩 3 枚嫌疑犯。第二次秤量剛好各處理 3 種結果，資訊量完美耗盡。

若沒有參考真幣，4 枚未知方向的硬幣無法用兩次秤量同時找出偽幣與方向——任何第一次秤量都會把 8 種情況壓成 3 種結果，必有一支裝超過 3 種，第二次切不開。原始 12 硬幣問題（無參考真幣）需要 3 次秤量。

$k$ 次秤量可解的硬幣數：

• 已知方向：$3^k$ 枚
• 未知方向（無參考真幣）：$\frac{3^k - 3}{2}$ 枚
• 未知方向（有參考真幣）：$\frac{3^k - 1}{2}$ 枚

常考：$k = 3$、未知方向、無參考真幣 → $\frac{27 - 3}{2} = 12$ 枚。

def chip_test(chips, is_good):
    while len(chips) > 1:
        kept = []
        i = 0
        while i + 1 < len(chips):
            a, b = chips[i], chips[i + 1]
            a_says = is_good(a, b)
            b_says = is_good(b, a)
            if a_says and b_says:
                kept.append(a)
            i += 2
        if len(chips) % 2 == 1:
            kept.append(chips[-1])
        chips = kept
    return chips[0]

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

有些課本採 1-indexed 並用 $\text{middle} = \lceil (\text{left} + \text{right}) / 2 \rceil$ 取中點（右偏中點）。邏輯完全一致，差別只在索引起點與偶數長度的中點位置。

陣列 $a[1..18] = [1, 2, 4, 6, 8, 10, 12, 13, 16, 18, 20, 28, 30, 35, 36, 41, 44, 49]$，找 $x = 33$。

第 4 回合後 left = 14 > right = 13，結束——$x = 33$ 不在陣列中。$33$ 夾在 $a[13] = 30$ 與 $a[14] = 35$ 之間。

def median_of_medians(arr, k):
    if len(arr) <= 5:
        return sorted(arr)[k - 1]
    groups = [sorted(arr[i:i + 5]) for i in range(0, len(arr), 5)]
    medians = [g[len(g) // 2] for g in groups]
    pivot = median_of_medians(medians, len(medians) // 2 + 1)
    L = [x for x in arr if x < pivot]
    E = [x for x in arr if x == pivot]
    G = [x for x in arr if x > pivot]
    if k <= len(L):
        return median_of_medians(L, k)
    if k <= len(L) + len(E):
        return pivot
    return median_of_medians(G, k - len(L) - len(E))


import random

def randomized_select(arr, k):
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    L = [x for x in arr if x < pivot]
    E = [x for x in arr if x == pivot]
    G = [x for x in arr if x > pivot]
    if k <= len(L):
        return randomized_select(L, k)
    elif k <= len(L) + len(E):
        return pivot
    return randomized_select(G, k - len(L) - len(E))

陣列 $a[1..27] = [7, 3, 6, 8, 1, 10, 4, 3, 8, 5, 7, 10, 0, 10, 2, 1, 4, 4, 13, 5, 0, 8, 9, 9, 2, 6, 1]$，$k = 16$。

分 6 組（前 5 組 5 個、最後一組 2 個）：

中位數集 $\{6, 5, 7, 4, 8, 6\}$ 排序後 $\{4, 5, 6, 6, 7, 8\}$，MoM = 6 → pivot。

以 6 分堆：

$|L| = 14 < 16 \leq 16 = |L| + |E|$ → 答案就是 pivot = 6，不用再遞迴。

常見錯誤：G4 的中位數誤寫成 5、G5 誤寫成 6。一定要先排序再取中間，不是「原始順序的第 3 個」。

假設 pivot 剛好依序抽到 21 → 9 → 12。

第一輪：pivot = 21。$L$ 共 13 個、$E$ 1 個、$G$ 11 個。$k = 8 \leq 13$ → 進 $L$。

第二輪：$L = [17, 3, 8, 12, 5, 14, 7, 19, 2, 11, 6, 15, 9]$，pivot = 9。$L' = [3, 8, 5, 7, 2, 6]$（6 個）、$E' = [9]$、$G' = [17, 12, 14, 19, 11, 15]$（6 個）。$k = 8 > 7$ → 進 $G'$ 找第 $8 - 7 = 1$ 小。

第三輪：pivot = 12。$L'' = [11]$、$E'' = [12]$、$G'' = [17, 14, 19, 15]$。$k = 1 \leq 1$ → 進 $L''$。

第四輪：$L'' = [11]$，直接回傳 11。

與 BFPRT 答案一致。差別：BFPRT pivot 固定為 MoM，穩但慢；Randomized 隨手抽，快但最差 $O(n^2)$。

def next_fit(items, C):
    bins = [0]
    for x in items:
        if bins[-1] + x > C:
            bins.append(x)
        else:
            bins[-1] += x
    return bins


def first_fit(items, C):
    bins = []
    for x in items:
        placed = False
        for i, used in enumerate(bins):
            if used + x <= C:
                bins[i] += x
                placed = True
                break
        if not placed:
            bins.append(x)
    return bins


def first_fit_decreasing(items, C):
    return first_fit(sorted(items, reverse=True), C)

物品 $[0.5, 0.7, 0.5, 0.2, 0.4, 0.2, 0.3, 0.1]$、$C = 1.0$：

• NF：0.5→Bin1（剩 0.5）；0.7→Bin1 塞不下開 Bin2（剩 0.3）；0.5→Bin2 塞不下開 Bin3（剩 0.5）；… 最終約 4~5 箱，浪費最多。
• FF：不排序、照原順序從頭找可用箱。大致 3~4 箱。
• FFD：如上例，3 箱，最佳。

結論：FFD 在這組資料上是最佳，也符合近似比最緊的直覺。