我在哪里可以得到一个“有用的”C + + 二进制搜索算法？

我需要一个与 C + + STL 容器兼容的二进制搜索算法，类似于标准库 <algorithm>头中的 std::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.

到目前为止，如果数据丢失，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。

46118 次浏览
小开

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

小开

他们有一组人:

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

搜寻:

On a separate note:

他们可能认为搜索集装箱可以得到不止一个结果。但是在偶尔的情况下，您只需要测试是否存在一个优化版本也是不错的。

小开

下界() :)

小开
最佳答案

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

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).

小开

检查这个函数，QBinaryFind:

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

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

范围内的项目[开始，结束] 必须按升序排序; 参见 qSort().

如果有许多 相同的价值，他们中的任何一个都可能是 returned. Use qLowerBound() or 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 (or 3 or 4)

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

小开

If std::lower_bound is too low-level for your liking, you might want to check 容器: : average _ multiset. 它是用二进制搜索作为排序向量实现的 std: : multiset 的一个插入式替换。

小开

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

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;


}
小开 
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 Initially, start=0 and end=9-1=8 现在，由于 start < = end; mid = 4; (array [ mid ]是5) ! = 3 现在，3在中间的左边，因为它小于5。因此，我们只搜索数组的左侧部分 因此，现在 start = 0和 end = 3; mid = 2。由于 array [ mid ] = = 3，因此我们得到了正在搜索的数字。因此，我们返回它的索引，它等于 mid。

小开

The shortest implementation, wondering why it's not included in the standard library:

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


提交答案