How to Implement a Binary Search Algorithm That Returns an Iterator in C ?

Binary Search Algorithm Returning Iterator in C

In C , the std::binary_search algorithm provides a convenient way to perform binary search on sorted containers. However, it only returns a boolean indicating whether the element exists, which may not be sufficient for some applications.

Requirement for Iterator-Returning Algorithm

The need arises for a binary search algorithm that returns an iterator pointing to the result rather than a boolean. This allows developers to access the actual element found or determine if it is not present in the container.

Implementing a Custom Binary Search Algorithm

Since there is no such function available in the standard library, a custom implementation can be crafted using other STL functions like std::lower_bound, std::upper_bound, or std::equal_range.

Sample Implementation

Here is a simple implementation that utilizes std::lower_bound:

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

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

Alternatively, Using a std::set

Another option is to employ a std::set, which maintains sorted elements and provides a method find(T key) that returns an iterator to the specified item. However, this approach might not be suitable if multiple instances of the same element are required in the container.

The above is the detailed content of How to Implement a Binary Search Algorithm That Returns an Iterator in C ?. For more information, please follow other related articles on the PHP Chinese website!