algorithm - Binary Search 可以/Is Binary Search 是一种贪心算法吗？

Question

我正在阅读关于 Binary search 的不同 Material ，我不清楚它是一个贪婪的二进制文件(在我看来它不是)或者，它可以是一个具有某些特定实现的贪婪算法吗？

如果它可以是贪心的，它有什么意义呢？如果通过选择局部最优来获得全局最优，而不重新考虑之前的选择，则不能保证二分查找的正确结果。

Answer 1

我想如果您从侧面斜视它，您会发现二分搜索是贪婪的，因为您试图在每一步中尽可能多地减少搜索空间。它恰好是搜索空间中的一种贪心算法，其结构既高效又总能找到正确答案。

我不习惯斜视。

也就是说二分搜索可以在传统的贪心算法中使用。例如，包装问题的贪心算法可能会要求您接下来选择“仍然可以容纳的最大可用项目”。可以使用二进制搜索来找到它。

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