在哪里可以找到“有用的”c++二进制搜索算法?

I need a binary search algorithm that is compatible with the C++ STL containers, something like std::binary_search in the standard library's <algorithm> header, but I need it to return the iterator that points at the result, not a simple boolean telling me if the element exists.

我需要一个与c++ STL容器兼容的二进制搜索算法，比如标准库的头中的std::binary_search，但是我需要它返回指向结果的迭代器，而不是一个简单的布尔值，告诉我元素是否存在。

(On a side note, what the hell was the standard committee thinking when they defined the API for binary_search?!)

(顺便说一句，当标准委员会定义binary_search的API时，他们到底在想什么呢?!)

My main concern here is that I need the speed of a binary search, so although I can find the data with other algorithms, as mentioned below, I want to take advantage of the fact that my data is sorted to get the benefits of a binary search, not a linear search.

我主要担心的是,我需要一个二叉搜索的速度,所以,虽然我能找到的数据与其他算法,正如下面所提到的,我想利用这一事实数据排序二叉搜索的好处,而不是一个线性搜索。

so far lower_bound and upper_bound fail if the datum is missing:

如果数据丢失，那么到目前为止，小写的绑定和大写的失败:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

Note: I'm also fine using an algorithm that doesn't belong to the std namespace as long as its compatible with containers. Like, say, boost::binary_search.

注意:使用不属于std名称空间的算法也没问题，只要它与容器兼容即可。比如说,boost::binary_search。

8 个解决方案

#1

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

没有这样的函数，但是您可以使用std::小写、std::upper_bound或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).

另一种解决方案是使用std::set，它保证元素的排序，并提供一个方法iterator find(T键)，该方法将迭代器返回给给定的项。但是，您的需求可能与使用集合不兼容(例如，如果需要多次存储相同的元素)。

#2

You should have a look at std::equal_range. It will return a pair of iterators to the range of all results.

您应该看看std: equal_range。它将返回一对迭代器到所有结果的范围。

#3

There is a set of them:

有一套:

http://www.sgi.com/tech/stl/table_of_contents.html

Search for:

搜索:

lower_bound
lower_bound
upper_bound
upper_bound
equal_range
equal_range
binary_search
binary_search

On a separate note:

在一个单独的注意:

They were probably thinking that searching containers could term up more than one result. But on the odd occasion where you just need to test for existence an optimized version would also be nice.

他们可能认为搜索容器可以得到多个结果。但在偶尔需要测试是否存在的情况下，优化后的版本也不错。

#4

If std::lower_bound is too low-level for your liking, you might want to check boost::container::flat_multiset. It is a drop-in replacement for std::multiset implemented as a sorted vector using binary search.

如果std::小写绑定太低级，不适合您的喜好，您可能需要检查boost::container::flat_multiset。这是对std::multiset的一种替代，它实现为使用二进制搜索的排序向量。

#5

std::lower_bound() :)

std::lower_bound():)

#6

Check this function, qBinaryFind:

检查这个函数,qBinaryFind:

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )
Performs a binary search of the range [begin, end) and returns the position of an occurrence of value. If there are no occurrences of value, returns end.

执行范围[开始，结束]的二进制搜索，并返回值出现的位置。如果没有出现值，返回结束。

The items in the range [begin, end) must be sorted in ascending order; see qSort().

范围内的项[开始，结束]必须按升序排序;看到qSort()。

If there are many occurrences of the same value, any one of them could be returned. Use qLowerBound() or qUpperBound() if you need finer control.

如果出现了许多相同值，则可以返回其中的任何一个。如果需要更好的控制，请使用qLowerBound()或qUpperBound()。

Example:

例子:
QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

The function is included in the <QtAlgorithms> header which is a part of the Qt library.

该函数包含在Qt库的一部分< qtalgims >标头中。

#7

A solution returning the position inside the range could be like this, using only operations on iterators (it should work even if iterator does not arithmetic):

返回该范围内的位置的解决方案可能是这样的，只使用迭代器上的操作(即使迭代器不计算，它也应该工作):

template <class InputIterator, typename T>
size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val)
{       
    const InputIterator beginIt = first;
    InputIterator element = first;
    size_t p = 0;
    size_t shift = 0;
    while((first <= last)) 
    {
        p = std::distance(beginIt, first);
        size_t u = std::distance(beginIt, last);
        size_t m = (p+u)/2;
        std::advance(element, m - shift);
        shift = m;
        if(*element == val) 
            return m; // value found at position  m
        if(val > *element)
            first = element++;
        else
            last  = element--;

    }
    // if you are here the value is not present in the list, 
    // however if there are the value should be at position u
    // (here p==u)
    return p;

}

#8

int BinarySearch(vector<int> array,int var)
{ 
    //array should be sorted in ascending order in this case  
    int start=0;
    int end=array.size()-1;
    while(start<=end){
        int mid=(start+end)/2;
        if(array[mid]==var){
            return mid;
        }
        else if(var<array[mid]){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }
    return 0;
}

Example: Consider an array, A=[1,2,3,4,5,6,7,8,9] Suppose you want to search the index of 3 Initially, start=0 and end=9-1=8 Now, since start<=end; mid=4; (array[mid] which is 5) !=3 Now, 3 lies to the left of mid as its smaller than 5. Therefore, we only search the left part of the array Hence, now start=0 and end=3; mid=2.Since array[mid]==3, hence we got the number we were searching for. Hence, we return its index which is equal to mid.

示例:考虑一个数组，A=[1、2、3、4、5、6、7、8、9]假设您最初要搜索3的索引，start=0, end=9-1=8，因为start<=end;中期= 4;(array[mid] = 5) =3现在，3位于mid的左边，小于5。因此，我们只搜索数组的左侧部分，因此，现在start=0, end=3;中期= 2。因为数组[mid]==3，所以我们得到了我们要搜索的数字。因此，我们返回它的指数，它等于中间值。

#1