例题10-6 分治法求解金块问题

分治法是一种分而治之的思想，将问题不断分解为小问题，直到小问题可以直接求解为止。对于金块问题，可以使用分治法求解。

具体思路如下：

1. 将金块分成两份，分别称为左金块和右金块。

2. 比较左金块和右金块的重量。

3. 如果左金块的重量大于右金块，说明假金块在左金块中，递归地对左金块进行求解。

4. 如果右金块的重量大于左金块，说明假金块在右金块中，递归地对右金块进行求解。

5. 如果左金块和右金块的重量相等，说明假金块就是剩下的那个金块。

代码如下：

def find_fake(gold):
    # 如果金块只有一个，直接返回
    if len(gold) == 1:
        return gold[0]
    
    # 将金块分成两份，分别称为左金块和右金块
    mid = len(gold) // 2
    left = gold[:mid]
    right = gold[mid:]
    
    # 比较左金块和右金块的重量
    left_weight = sum(left)
    right_weight = sum(right)
    
    # 如果左金块的重量大于右金块，说明假金块在左金块中
    if left_weight > right_weight:
        return find_fake(left)
    # 如果右金块的重量大于左金块，说明假金块在右金块中
    elif right_weight > left_weight:
        return find_fake(right)
    # 如果左金块和右金块的重量相等，说明假金块就是剩下的那个金块
    else:
        return gold[-1]

测试代码如下：

gold = [10, 10, 10, 10, 10, 10, 10, 10, 10, 9]
print(find_fake(gold))  # 输出 9

时间复杂度为 $O(n\log n)$。