二進制搜索是/是二進制搜索貪婪算法？

我正在閱讀關於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

二進制搜索是/是二進制搜索貪婪算法？

回答

相關問題