要素の位置を返す二分探索アルゴリズムを C で実装するにはどうすればよいですか?

「便利な」C バイナリ検索アルゴリズムの取得

C STL は binary_search アルゴリズムを提供しますが、返されるのは binary_search アルゴリズムかどうかを示すブール値だけです。要素が存在します。要素の正確な位置が必要な場合には、より包括的なアルゴリズムが必要です。

1 つのオプションは、カスタム二分検索関数を作成することです。簡単な実装を次に示します。

<code class="cpp">template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val) {
    // Find the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}</code>

もう 1 つのアプローチは、要素を自動的に順序付けし、項目にイテレータを返す find(T key) メソッドを提供する std::set を使用することです。ただし、データに重複する値が含まれる可能性がある場合、これは適切ではない可能性があります。

速度が重要な状況では、二分探索の利点を活用することが重要です。 Lower_bound アルゴリズムと upper_bound アルゴリズムは、要素が存在しない場合、終了反復子を返さない可能性があるため、不適切になる可能性があります。上記で提供されている binary_find 関数はこの問題に対処し、正しい動作を保証します。

以上が要素の位置を返す二分探索アルゴリズムを C で実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。