哪里可以得到“有用”的信息？ C++ 二分查找算法？

Question

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

（顺便说一句，标准委员会在为binary_search定义API时到底在想什么？！）

我这里主要关心的是我需要二分搜索的速度，所以虽然我可以用其他算法找到数据，如下所述，我想利用我的数据已排序的事实来获得二分搜索而不是线性搜索的好处。

到目前为止，如果缺少数据，lower_bound 和 upper_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。

Answer 1

没有这样的函数，但您可以使用 std::lower_bound 编写一个简单的函数，std::upper_bound< /a> 或 std::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 ，它保证元素的顺序并提供返回的迭代器 find(T key) 方法给定项目的迭代器。 但是，您的要求可能与集合的使用不兼容（例如，如果您需要多次存储相同的元素）。

Answer 2

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

Answer 3

有一组：

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

搜索：

• lower_bound
• upper_bound
• equal_range
• binary_search

另请注意：

他们可能认为搜索容器可以得出多个结果。 但在奇怪的情况下，您只需要测试是否存在，优化版本也会很好。

Answer 4

如果 std::lower_bound 对于您的喜好来说太低级，您可能需要检查 boost::container::flat_multiset。
它是 std::multiset 的直接替代品，使用二分搜索实现为排序向量。

Answer 5

最短的实现，想知道为什么它没有包含在标准库中：

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

Answer 6

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
现在，由于 start<=end; 中=4； (数组[mid]为5) !=3
现在，3 位于 mid 的左侧，因为它小于 5。因此，我们只搜索数组的左侧部分
因此，现在 start=0 和 end=3； mid=2.由于 array[mid]==3，因此我们得到了要搜索的数字。 因此，我们返回其索引，该索引等于 mid。

Answer 7

检查这个函数，qBinaryFind：

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value ) 
  

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

范围 [begin, end) 中的项目
必须按升序排序； 看
qSort()。

如果出现多次
相同的值，其中任何一个都可以
回。 使用 qLowerBound() 或
qUpperBound() 如果你需要更精细
控制。

示例：

QVector;   向量； 
   向量 <<   3<<;   3<<;   6《》   6《》   6《》   8； 

   QVector::迭代器 i = 
           qBinaryFind(vect.begin(), vect.end(), 6); 
   // i == vect.begin() + 2 （或 3 或 4） 
  

该函数包含在 标头中，该标头是 Qt 库。

Answer 8

std::lower_bound() :)

Answer 9

返回范围内位置的解决方案可能如下所示，仅使用迭代器上的操作（即使迭代器不进行算术，它也应该可以工作）：

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-p)/2;  // overflow safe (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;

}