問題描述
我需要一個(gè)與 C++ STL 容器兼容的二進(jìn)制搜索算法，比如標(biāo)準(zhǔn)庫的 標(biāo)頭中的 std::binary_search，但我需要它返回指向結(jié)果的迭代器，而不是告訴我元素是否存在的簡單布爾值.
I need a binary search algorithm that is compatible with the C++ STL containers, something like std::binary_search in 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.
(順便說一句，標(biāo)準(zhǔn)委員會(huì)在為 binary_search 定義 API 時(shí)到底在想什么?！)
(On a side note, what the hell was the standard committee thinking when they defined the API for binary_search?!)
我在這里主要關(guān)心的是我需要二進(jìn)制搜索的速度，所以雖然我可以用其他算法找到數(shù)據(jù)，如下所述，我想利用我的數(shù)據(jù)被排序的事實(shí)來獲得好處屬于二分搜索，而不是線性搜索.
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 如果數(shù)據(jù)丟失則失敗:
so far lower_bound and upper_bound fail if the datum is missing:
//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.
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.
推薦答案
沒有這樣的函數(shù)，但是你可以用 std::lower_bound, std::upper_bound 或 std::equal_range.
There is no such functions, but you can write a simple one using std::lower_bound, std::upper_bound or std::equal_range.
一個(gè)簡單的實(shí)現(xiàn)可能是
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)到給定的項(xiàng)目.但是，您的要求可能與集合的使用不兼容(例如，如果您需要多次存儲(chǔ)相同的元素).
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).
這篇關(guān)于我在哪里可以得到一個(gè)“有用的"?C++二分查找算法?的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！