How to Implement a Binary Search Algorithm in C That Returns the Element\'s Location?

Getting a "Useful" C Binary Search Algorithm

The C STL provides a binary_search algorithm, but it only returns a boolean indicating whether the element exists. For cases where the exact location of the element is required, there is a need for a more comprehensive algorithm.

One option is to create a custom binary search function. Here's a simple implementation:

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

Another approach is to use a std::set, which automatically orders elements and provides a find(T key) method that returns an iterator to the item. However, this may not be suitable if the data can contain duplicate values.

For situations where speed is critical, it is important to take advantage of the benefits of a binary search. Lower_bound and upper_bound algorithms can be inadequate when the element does not exist, as they may not return the end iterator. The binary_find function provided above addresses this issue and ensures the correct behavior.

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