二进制搜索是/是二进制搜索贪婪算法？

我正在阅读关于Binary search的不同材料，但我不清楚它是否是一个贪婪的二进制文件（在我看来它不是），或者它可以是一种具有某种特定实现的贪婪算法吗？二进制搜索是/是二进制搜索贪婪算法？

如果它可以是贪婪的，它是如何有意义的？如果全局最优是通过选择局部最优而获得的，而不重新考虑先前的选择，则它不能保证二分搜索的正确结果。

来源

2017-07-25 Stas

假设您正在寻找位于索引100处的8位值范围（1-256）中的元素。您的二进制搜索进度将考虑以下指数：

128？太大
64？太小
64 + 32？太小
64 + 32 + 16？太大
64 + 32 + 8？太大
64 + 32 + 4？发现

很容易注意到，在每一步中，您正在测试尚未测试的最重要的位，如果它没有溢出结果，它将被添加到部分解决方案中直到找到最终结果。

因此，按照贪心选择的特点，可以指出：

有数量的8位组成找到了候选集。
贪婪的选择考虑在每一步中最重要的位尚未使用。
检查该位是否可以添加到最终解决方案本地查看该位和目前组装的结果。
如果总和没有溢出，则该位成为最终解决方案的一部分。
最终的解决方案可以识别何时合成和等于搜索的结果。

当然不需要回溯，所以这是一个完美的贪婪算法。

来源

2017-07-25 13:56:30 jszpilewski

是的，二进制搜索是一种贪婪算法，但另一种更准确的方法是，它不是。 –

嗯。有趣的，谢谢。有更准确的定义吗？ – Stas

@Stas这不是正式的。更类似于通过将表示最终数字的位相加来代替在二分搜索中丢弃一半输入的想法。最终可以实现相同的目标（log（n），甚至尝试相同的索引），同时严格满足贪婪算法的期望。当然，可能需要进行一些调整以使输入大小为2的幂。另一个问题是二进制搜索甚至不认为数字是由比特组成的。但是这两种方法仍然有一些共同之处。 – jszpilewski

我想如果你斜着看它，二分搜索是贪婪的，因为你试图在每一步中尽可能地减少你的搜索空间。它恰好是一个搜索领域的贪婪算法，其结构使得它既高效又可能找到正确的答案。

我不倾向于如此斜视。

这表示二进制搜索可以在传统的贪婪算法中使用。作为一个例子，一个包装问题的贪婪算法会要求你接下来选择“仍然适合的最大可用物品”。二进制搜索可以用来找到它。

相反，贪心算法可用于创建非常适合二分查找的数据结构。请参阅https://en.wikipedia.org/wiki/Geometry_of_binary_search_trees#Greedy_algorithm

来源

2017-07-25 14:04:57 btilly

二进制搜索是/是二进制搜索贪婪算法？

回答

相关问题