How to Find Element Index with Binary Search in C ?

Efficient Binary Search Implementation in C

Finding the index or iterator of an element in a sorted container is a fundamental operation in C . However, the standard library's std::binary_search algorithm only returns a boolean indicating the existence of the element, not its position.

Consider the case where the container is sorted, and a binary search algorithm is preferable for efficiency reasons. An implementation that addresses this need is required.

Custom Iterative Binary Search

One approach is to implement a custom iterative binary search algorithm. Here's an example implementation:

<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>

This algorithm uses std::lower_bound to efficiently find the iterator pointing to the searched element. If the found value does not match val, it returns the end() iterator.

Alternative Solutions

Another option is to employ a std::set, which guarantees element ordering and provides a find(T key) method that returns an iterator to the given item. However, this may not be suitable for cases where duplicate elements are required.

The above is the detailed content of How to Find Element Index with Binary Search in C ?. For more information, please follow other related articles on the PHP Chinese website!