我在哪里可以获得“有用的”C++二分搜索算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/446296/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Where can I get a "useful" C++ binary search algorithm?
提问by Robert Gould
I need a binary search algorithm that is compatible with the C++ STL containers, something like std::binary_searchin 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标准库的<algorithm>头文件，但我需要它返回指向结果的迭代器，而不是一个简单的布尔值，告诉我元素是否存在。
(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_boundand upper_boundfail if the datum is missing:
到目前为止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
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。
采纳答案by Luc Touraille
There is no such functions, but you can write a simple one using std::lower_bound, std::upper_boundor std::equal_range.
没有这样的函数，但您可以使用std::lower_bound,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).
另一种解决方案是使用 a std::set，它保证元素的顺序并提供一个方法iterator find(T key)来返回给定项的迭代器。但是，您的要求可能与集合的使用不兼容（例如，如果您需要多次存储相同的元素）。
回答by Luc Hermitte
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。它将返回一对迭代器到所有结果的范围。
回答by Martin York
There is a set of them:
有一组：
http://www.sgi.com/tech/stl/table_of_contents.html
http://www.sgi.com/tech/stl/table_of_contents.html
Search for:
搜索：
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.
他们可能认为搜索容器可以得出不止一个结果。但是在您只需要测试是否存在的奇怪情况下，优化版本也会很好。
回答by ZunTzu
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::lower_bound 对您来说太低级，您可能需要检查boost::container::flat_multiset。它是 std::multiset 的替代品，使用二分搜索实现为排序向量。
回答by Lawand
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().
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.
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)
RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )对范围 [begin, end) 执行二分搜索并返回 value 出现的位置。如果没有出现 value，则返回 end。
[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 (or 3 or 4)
The function is included in the <QtAlgorithms>header which is a part of the Qtlibrary.
该函数包含在<QtAlgorithms>作为Qt库一部分的头文件中。
回答by trozen
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;
}
From https://en.cppreference.com/w/cpp/algorithm/lower_bound
回答by Michele Belotti
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-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;
}
回答by Siddharth Kumar Shukla
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 and end=9-1=8 现在, 因为开始<=结束; 中=4；(array[mid] which is 5) !=3 现在，3 位于 mid 的左边，因为它小于 5。因此，我们只搜索数组的左边部分 因此，现在 start=0 和 end=3；mid=2.由于array[mid]==3，因此我们得到了我们要搜索的数字。因此，我们返回其等于 mid 的索引。
回答by moogs
std::lower_bound() :)
std::lower_bound() :)
