关于算法:搜索算法系列-折半搜索

黄金问题

当初有 n 块黄金，每块黄金的品质为 w[i]，小明能够一次性搬运品质不超过 m 的物体，问小明一次至少能运走多少品质的黄金？

对于该问题，浏览过我之前讲过的深度优先搜寻应该不难写出如下代码。

def dfs(cur, total, status = set()):
    for i in range(cur, n):
        if total + w[i] > m:
            continue
        status.add(total + w[i])
        dfs(i+1, total + w[i])
    return status

对于 w = [1,8,6]，m = 10 的数据，能够失去 status = {1,8,6,9,7}，也就是 w 可能组合出的不超过 m 的所有值，取其最大值即为该问题的答案。

然而该解法的工夫复杂度太高了，为 n!（这里还与 m 值无关，要真有这么大都别玩了）， 其实这里能够动静布局 ，咱们如何应答更大 n 值的状况？

对于规模为 10 的状况，其复杂度在 400w，而对于规模为 5 的状况，其复杂度在 100，也就是说如果咱们可能把一个规模为 10 的问题分解成两个规模为 5 的问题，那么工夫复杂度只须要 100 + 100 = 200。速度较之前晋升了 2 万倍。

那么咱们如何通过两个规模为 5 的解得出规模为 10 的解呢？

def solution(n, m, w):
    def dfs(cur, end, total = 0, status = set()):
        for i in range(cur, end):
            if total + w[i] > m:
                continue
            status.add(total + w[i])
            dfs(i+1, end, total + w[i])
        return status
    
    ans1 = sorted(list(dfs(0, n//2)))
    ans2 = sorted(list(dfs(n//2, n)))
    ans  = max(ans1)
    for i in ans2:
        t = binary_search_last_equal_or_lower(m-i, ans1)
        ans = max(ans, t+i)
    return ans

上述代码中，咱们遍历 ans2 列表，在 ans1 寻找最大的且与 i 相加不超过 m 的值（反过来也行），并在遍历的过程中动静更新 ans 的值，遍历完结，ans 即咱们想要的答案。

对于最终的 ans，有如下三种可能。

1. ans1[i] + ans2[j]
2. max(ans1)
3. max(ans2)

其中状况 1 在遍历时实现，状况 2 在 ans 赋初值时实现，状况 3 在 ans1 没有值能够与 m - i 结对时实现（这时候二分查找返回 0 值）。

本文示例题目与 acwing 171. 送礼物统一，读者可自行尝试提交，验证本人代码的正确性。