私はBinary searchについてさまざまな資料を読んでいますが、貪欲なバイナリ（それは私には似ていないようです）か、それとも特定の実装で欲張りなアルゴリズムですか？バイナリサーチはバイナリサーチであり、貪欲なアルゴリズムである可能性がありますか？
それが欲しい場合は、どのように意味がありますか？前回の選択を再検討することなく、局所最適値を選択することによって大域的最適値が得られる場合、バイナリ検索の正しい結果を保証することはできない。
インデックス100の要素を8ビットの値の範囲（1〜256）で探しているとします。バイナリ検索の進行状況は、次のインデックスを考慮します：
発見すべてのステップであなたがいないテストまだ最上位ビットをテストしていることに注意することは簡単です、それは結果がオーバーフローしない場合、最終的な結果が発見されるまで、それは部分的な解決に追加されます。貪欲な選択肢の
だから、次のような特徴を指摘することができます。
これは完璧な欲張りアルゴリズムなので、もちろんバックトラックは必要ありません。
もしあなたが横向きに横たわっていたら、バイナリ検索はあなたが各ステップでできる限り多くの検索スペースを削減しようとしているという意味で欲張りです。効率的であり、いつも正解を見つける可能性が高い構造を持つ検索スペースでは、貪欲なアルゴリズムにすぎません。
私はそんなにうんざりしません。
このバイナリ検索は、伝統的な欲張りアルゴリズムの内部で使用できます。一例として、詰め込み問題の貪欲なアルゴリズムは、次に「依然として適合可能な最大の利用可能なアイテム」を選択するよう求めるかもしれません。バイナリ検索を使用してそれを見つけることができます。逆に、欲張りアルゴリズムを使用して、バイナリ検索に適したデータ構造を作成することができます。たとえば、https://en.wikipedia.org/wiki/Geometry_of_binary_search_trees#Greedy_algorithm
はい、バイナリ検索は欲張りアルゴリズムですが、別のより正確な方法ではありません。 –
Hmm。興味深い、ありがとう。それについてもっと正確な定義がありますか？ – Stas
@Stasこれは正式なものではありません。最終的な数を表すビットを足し合わせることで、バイナリ検索で入力の半分を捨てるという考えを置き換える方がいいです。最終的には、同じ目標（log（n）と同じ指標を試しても同じ目標）を達成しながら、欲張りアルゴリズムの期待に厳密に合致することができました。もちろん、入力サイズを2の累乗にするための調整が必要な場合もあります。別の問題は、バイナリ検索でも数字がビットで構成されているとはみなされないということです。しかし、これらの2つのアプローチには共通点があります。 – jszpilewski