STL 中的二分搜索算法

原文：https://www.studytonight.com/cpp/stl/stl-searching

如果元素出现在给定的范围内，此函数返回布尔值 true，否则返回布尔值 false。binary_search()有两种变体:

• binary_search(first, last, value):如果存在满足条件(！(一<值)& &！(值< a))在给定的范围内，即从第一个到最后一个，换句话说，运算符(
• binary_search(first, last, value, compare_function):如果在给定的范围内存在一个元素，即从第一个到最后一个，这个版本返回 true。

注意，第一个和最后一个是迭代器，最后一个指向的元素被排除在搜索之外。

这里我们不需要首先对元素容器进行排序，binary_search()将为我们完成所有的工作，我们只需要给出一个要搜索的范围和值。

#include <iostream>    
#include <algorithm>
#include <vector>
using namespace std;

bool **compare_string_by_length** (string i,string j)
{
    return (i.size() == j.size());
}

int main () 
{
    int inputs[] = {7,8,4,1,6,5,9,4};
    vector<int> v(inputs, inputs+8);

    cout<<**binary_search**(**v**.begin() , **v**.end() , 7 );  *//prints 1 , Boolean true*

    cout<<**binary_search**(**v**.begin() , **v**.end() , 217); *//prints 0 , Boolean false*

    */* compare_function can be used to search 
    non numeric elements based on their properties */* 

    string s[] = { "test" , "abcdf" , "efghijkl" , "pop" };

    cout<<binary_search(s, s+4, "nickt" , **compare_string_by_length**);
    */* search for the string in s which have same length as of "nicky" */*

}

STL 中的等距离算法equal_range

equal_range()返回一对迭代器，其中迭代器代表给定范围内等于给定值或满足 compare_function 的元素的子范围。给定的范围应该已经排序。相等范围有两种变化:

• equal_range(first, last, value):返回一对迭代器，表示元素等于值的(第一个，最后一个)的子范围。
• equal_range(first, last, value, compare_function):返回一对迭代器，表示(第一个，最后一个)的子范围，其中的元素满足 compare_function 的值。

#include <iostream>    
#include <algorithm>    
#include <vector>
using namespace std;

bool **compare_function** (int i,int j) 
{ 
    return (i <= j); 
}

int main () 
{
    int input[] = {1,1,1,2,2,2,3,3,6,7,7,7,7,7,8,9};
    vector <int>v(input, input+16);

    **pair**< vector<int>::iterator, vector<int>::iterator > sub_range;
    */* defining the pair of two iterators to an integer vector */*

    sub_range = **equal_range** (v.begin(), v.end(), 2);
    */* now sub_range.first points to 4th element in the vector v and 
     sub_range.second points to 7th element , 
     note that sub_range.secong points to the element 
     which is next to the element in the subrange  */* 

    sub_range = **equal_range** (v.begin(), v.end(), 20, compare_function);
    */* sub_range.first points to first element in the vector v , 
    as it satisfy the condition exerted by compare_function , <= , 
     sub_range.second points to 7th element in the vector . */*
}</int>