4.4.6  搜索算法

4.4.6 搜索算法

1.binary_search（）算法

STL针对有序区间提供了搜索算法binary_search（），可用以实现在有序区间中搜寻指定元素。其原型为：

以上两种算法形式均用来判断有序区间［_First，_Last］中是否包含值为_Val的元素。_Comp是一个可有可无的二元判断式，用来作为排序准则。如果搜寻被查找元素的位置，应使用lower_bound（）、upper_bound（）和equal_range（）。

使用binary_search（）算法之前，程序员要确保被搜索的区间必须是有序的。

2.includes（）算法

includes（）算法可用于在指定源区间中检查若干值是否存在。Visual C＋＋ 6.0的msdn文档中提供的该算法的原型为：

而C＋＋语言的ISO/IEC14482标准中提供了两种函数形式，其中一种与上述形式相同，另一种形式如下所示：

3.搜索第一个或（和）最后一个可能位置

STL还提供了lower_bound（）、equal_range（）和upper_bound（）算法。lower_bound（）算法返回第一个“大于等于value”的元素位置。这是被查找元素的第一个位置。equal_range（）算法和lower_bound（）算法一样，要求被搜索的源区间是已序的。equal_range（）算法的返回值其实是lower_bound（）和upper_bound（）的共同返回值。

注意：使用lower_bound（）和upper_bound（）算法时，如果未找到指定的元素，其返回值end（）指向位置。

以上3个算法的使用方法见例4-31。

例4-31

例4-31的执行效果如图4-31所示。

图4-31 例4-31的执行效果