gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:08:48 29 4
gpt4 key购买 nike

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

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

最佳答案

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

我不习惯斜视。

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

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

关于algorithm - Binary Search 可以/Is Binary Search 是一种贪心算法吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45303599/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com