首页 文章

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

提问于
浏览
90

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

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

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

到目前为止 lower_boundupper_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

Note: I 'm also fine using an algorithm that doesn' t属于std命名空间,只要它与容器兼容即可 . 比方说, boost::binary_search .

9 回答

  • 8

    没有这样的功能,但您可以使用std::lower_boundstd::upper_boundstd::equal_range编写一个简单的功能 .

    一个简单的实现可能是

    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) ,它返回给定项的迭代器 . 但是,您的要求可能与集合的使用不兼容(例如,如果您需要多次存储相同的元素) .

  • 6

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

  • 82

    有一组:

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

    搜索:

    另请注意:

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

  • 1

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

  • 1

    std :: lower_bound():)

  • 0

    检查此功能,qBinaryFind

    RandomAccessIterator qBinaryFind(RandomAccessIterator begin,RandomAccessIterator end,const T&value)
    对范围[begin,end]执行二进制搜索,并返回值出现的位置 . 如果没有出现值,则返回结束 . 范围[开始,结束]中的项目必须按升序排序;见qSort() . 如果出现多次相同的值,则可以返回其中任何一个值 . 如果需要更精细的控制,请使用qLowerBound()或qUpperBound() . 示例:QVector <int> vect;
    vect << 3 << 3 << 6 << 6 << 6 << 8;

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

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

  • 0

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

    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;
    
    }
    
  • 0
    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现在,自从开始<=结束;中期= 4; (array [mid]是5)!= 3现在,3位于mid的左边,因为它小于5.因此,我们只搜索数组的左边部分因此,现在start = 0和end = 3; mid = 2.Since array [mid] == 3,因此我们得到了我们要搜索的数字 . 因此,我们返回其等于mid的索引 .

  • 3

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

    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

相关问题