二进制搜索是贪婪算法吗?

我猜如果你斜视它,二进制搜索是贪婪的,因为你试图在每一步中尽可能减少搜索空间。它恰好是搜索空间中的一个贪婪算法,其结构使其既高效,又总是可能找到正确的答案。

也就是说,二进制搜索可以在传统的贪婪算法中使用。例如,对于一个包装问题,一个贪婪算法可能会要求您接下来选择“仍然适合的最大可用项”。可以使用二进制搜索来找到它。

相反,可以使用贪心算法创建非常适合二进制搜索的数据结构。参见示例 https://en.wikipedia.org/wiki/Geometry_of_binary_search_trees#Greedy_algorithm

• 128 ? 太大了
• 64 ? 太小了
• 64 + 32 + 16 ? 太大了
• 64 + 32 + 8 ? 太大了
• 64 + 32 + 4 ? 建立

很容易注意到,在每个步骤中,您都在测试尚未测试的最高有效位,如果它没有溢出结果,则将其添加到部分解中,直到找到最终结果。

因此,可以指出贪婪选择的以下特征:

2. 贪婪选择在每个步骤中考虑尚未使用的最重要位。
3. 检查该位是否可以添加到最终解决方案中,局部查看位和迄今为止组装的结果。