Python（分治算法）问题 A: 找出伪币

题目描述

给你一个装有n枚硬币的袋子。
n枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。
你的任务是找出这枚伪造的硬币。

输入

测试数据有多行，第一行是金币的数量n(n为正整数,并且n<=5000000)；
接下来一行是n枚硬币的重量，用空格隔开。

输出

输出假币的位置及重量，用空格隔开。

样例输入

4
43 43 43 1 

样例输出

4 1

解答（分治算法）：

# 二分法求列表中最小值及下标 
def fun(ls, lt, rt, res):
    # 1.[lt,rt]区间的元素个数小于等于2，直接求解
    if rt - lt < 2:
        res[0] = lt  # 存下标，后同
        res[1] = ls[lt]  # 存值，后同
        if ls[lt] > ls[rt]:
            res[0] = rt
            res[1] = ls[rt]
        return
    mid = (lt + rt) // 2
    lres = [0] * 2
    rres = [0] * 2
    # lres和rres分别用于存放左右两个区间的目标值和下标
    # 左半区间递归
    fun(ls, lt, mid, lres)
    # 右半区间递归
    fun(ls, mid + 1, rt, rres)
    # 合并
    if lres[1] < rres[1]:
        res[0] = lres[0]
        res[1] = lres[1]
    else:
        res[0] = rres[0]
        res[1] = rres[1]

n = int(input())
ls = list(map(int, input().split()))
res = [0] * 2
# res用于保存伪币的下标和值
fun(ls, 0, len(ls) - 1, res)
print(res[0] + 1, res[1])

答案不唯一，必定有更加优化的解法欢迎分享