CUJ：标准库：标准库中的搜索算法(4)

来源：互联网   发布日期：2011-10-01 18:36:02   浏览：10054次  

int*first=

std::lower_bound(A 0,A 10,5);

int*last =

std::upper_bound(A 0,A 10,5);

名字first和last暗示了区别：lower_bound()返回第一个你正在寻找的数值(对本例，是&A[3])，而upper_bound()返回最后一个你正寻找的值的下一个的iterator(对本例，是&A[7])。如果你搜索的值不存在，你将得到如果它存在的话，应该位于的位置。和前面一样，我们可以写：

int*first=

std::lower_bound(A 0,A 10,6);

int*last =

std::upper_bound(A 0,A 10,6);

first和last都将等于&A[7]，因为这是6在不违背排序时可以插入的唯一位置。

实践中，你看不到lower_bound()的调用后面立即跟一个upper_bound()。如果你同时需要这两个信息，那正是引入最后一个二分搜索算法的原因：equal_range()返回一个pair，第一个元素是lower_bound()将要返回的值，第二个元素是upper_bound()的返回值。

直到此时，我在讨论中故意比较粗略：我说了lower_bound()和upper_bound()找一个值，但没有正确说明它的含义。如果你写

iteratori=

std::lower_bound(first,last,x);

而且搜寻成功，你保证*i和x相等吗？不一定！lower_bound()和upper_bound()从不对等价性进行测试（WQ注：逻辑相等，使用operator==()）。它们使用你提供的比较函数：operator<()或其它一些功能象“lessthan”的比较函数。这意味着在*i不小于x并且x不小于*i时，搜索成功（WQ注，即等值性，数学相等）。

这个区别看起来象吹毛求疵，但它不是。假如你一些具有很多字段的复杂记录，你使用其中的一个字段作为排序的key值（比如，人的姓）。两个记录可能有相同的key值，于是，即使所有其它子段都是不同的，它们哪一个也不小于另外一个。

一旦开始想到记录和key值，二分搜索的另外一个问题就变得很自然了：你能用二分搜索根据key来搜索记录吗？更具体些，假设我们定义了一个structX：

structX{

intid;

...//otherfields

};

再假设有一个vector<X>，根据元素的id进行过排序。你如何使用二分搜索来找到一个指定id（比如148）的X？

一个方法是创建一个有着指定的id哑X对象，并在二分搜索中使用它：

Xdummy;

dummy.id=148;

vector<X>::iterator

=lower_bound(v.begin(),v.end(),

赞助本站