Where can I get a “useful” C++ binary search algorithm?

by

There is no such functions, but you can write a simple one using std::lower_bound, std::upper_bound or std::equal_range.

A simple implementation could be

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 && !(val < *i))
        return i; // found
    else
        return end; // not found
}

Another solution would be to use a std::set, which guarantees the ordering of the elements and provides a method iterator find(T key) that returns an iterator to the given item. However, your requirements might not be compatible with the use of a set (for example if you need to store the same element multiple times).

More Related Contents:

  1. std::transform() and toupper(), no matching function
  2. How to get a random element from a C++ container?
  3. c++ sort keeping track of indices [duplicate]
  4. Reorder vector using a vector of indices [duplicate]
  5. How can I sort an STL map by value?
  6. How can std::make_heap be implemented while making at most 3N comparisons?
  7. What is the right approach when using STL container for median calculation?
  8. std::back_inserter for a std::set?
  9. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  10. Why there is no std::copy_if algorithm?
  11. stl ordering – strict weak ordering
  12. Order Statistic Tree in C++
  13. What is the difference between palindrome permutation and permutation? [closed]
  14. In which scenario do I use a particular STL container?
  15. What are the complexity guarantees of the standard containers?
  16. How do I sort a std::vector by the values of a different std::vector?
  17. Why should one not derive from c++ std string class?
  18. Why can’t simple initialize (with braces) 2D std::array? [duplicate]
  19. Is it safe to assume that STL vector storage is always contiguous?
  20. Why can’t we declare a std::vector?
  21. Efficient way of reading a file into an std::vector?
  22. Determine if a type is an STL container at compile time
  23. Removing item from vector while iterating?
  24. std::map emplace without copying value
  25. C++ Double Address Operator? (&&)
  26. Sorting a std::vector by the string?
  27. Fast n choose k mod p for large n?
  28. STL remove doesn’t work as expected?
  29. Print 2-D Array in clockwise expanding spiral from center
  30. How to rotate a N x N matrix by 90 degrees? [closed]

Leave a Comment