我在哪里可以获得“有用的”C ++二进制搜索算法?

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

(另一方面,当他们为binary_search定义API时,标准委员会在想什么?!)

我主要担心的是我需要二进制搜索的速度,所以尽管我可以用其他算法找到数据,如下所述,我想利用我的数据被排序以获得二进制的好处这一事实 搜索,而不是线性搜索。

到目前为止boost::binary_searchupper_bound如果缺少原点则失败:

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

注意:只要与容器兼容,我也可以使用不属于std命名空间的算法。 比方说,像boost::binary_search

Robert Gould asked 2019-08-13T23:13:45Z
9个解决方案
84 votes

没有这样的功能,但您可以使用std::set,std::setstd::set编写一个简单的功能。

一个简单的实现可能是

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
}

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

Luc Touraille answered 2019-08-13T23:14:13Z
8 votes

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

Luc Hermitte answered 2019-08-13T23:14:38Z
6 votes

有一组:

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

搜索:

  • LOWER_BOUND
  • UPPER_BOUND
  • equal_range
  • binary_search

另请注意:

他们可能认为搜索容器可能会产生不止一个结果。 但在奇怪的情况下,你只需要测试存在,优化版本也会很好。

Martin York answered 2019-08-13T23:15:58Z
3 votes

如果你喜欢std :: lower_bound太低级别,你可能想检查一下boost :: container :: flat_multiset。它是使用二进制搜索实现为排序向量的std :: multiset的替代品。

ZunTzu answered 2019-08-13T23:16:23Z
1 votes

std :: lower_bound():)

moogs answered 2019-08-13T23:16:48Z
1 votes

检查这个函数,qBinaryFind:

<QtAlgorithms>

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

范围内的项目[开始,结束]   必须按升序排序; 看到  快速排序()。

如果发生了很多次   相同的价值,其中任何一个都可以   回。 使用qLowerBound()或   qUpperBound()如果你需要更精细   控制。

例:

<QtAlgorithms>

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

Lawand answered 2019-08-13T23:17:54Z
0 votes

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

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;

}
Michele Belotti answered 2019-08-13T23:18:19Z
0 votes
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;
}

示例:考虑一个数组,A = [1,2,3,4,5,6,7,8,9]假设您要搜索索引3最初,start = 0和end = 9-1 = 8现在,从开始&lt; =结束;中期= 4; (array [mid]是5)!= 3现在,3位于mid的左侧,因为它小于5.因此,我们只搜索数组的左侧部分因此,现在start = 0和end = 3; mid = 2.由于数组[mid] == 3,因此我们得到了我们要搜索的数字。 因此,我们返回其等于mid的指数。

Siddharth Kumar Shukla answered 2019-08-13T23:18:45Z
0 votes

最短的实现,想知道它为什么不包含在标准库中:

template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced 
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare. 
    // This is stricter than lower_bound requirement (see above)

    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}

来自[https://en.cppreference.com/w/cpp/algorithm/lower_bound]

trozen answered 2019-08-13T23:19:18Z
translate from https://stackoverflow.com:/questions/446296/where-can-i-get-a-useful-c-binary-search-algorithm