在已序区间中搜寻某元素
检查某个元素是否存在
bool binary_search(beg,end,const T& value)
bool binary_search(beg,end,const T& value,op)
(1)两种形式都用来判断已序区间[beg,end)中是否包含“和value等值”的元素;
(2)op是一个可有可无的二元判断式,用来作为排序准则:
op(elem1,elem2)
(3)如果想要获得被搜寻元素的位置,应使用lower_bound(),upper_bound()或equal_range();
(4)调用者必须确保进入算法之际,该区间已序(在指定的排序准则作用下);
(5)复杂度:如果搭配随机存取迭代器,则为对数复杂度,否则为线性复杂度;
代码示例:
#include"fuzhu.h" using namespace std; int main() { list<int> coll; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); if(binary_search(coll.begin(),coll.end(),5)) { cout<<"5 is present"<<endl; } else { cout<<"5 is not presnet"<<endl; } if(binary_search(coll.begin(),coll.end(),42)) { cout<<"42 is present"<<endl; } else { cout<<"42 is not presnet"<<endl; } system("pause"); return 0; }
检查若干个值是否存在
bool includes(beg,end,searchBeg,searchEnd)
bool includes(beg,end,searchBeg,searchEnd,op)
(1)两种形式都用来判断已序序列[beg,end)是否包含另一个已序序列[searchBeg,searchEnd)的全部元素,也就是说对于[searchBeg,searchEnd)中的每一个元素,如果[beg,end)必有一个对应的相等元素,那么[searchBeg,searchEnd)肯定是[beg,end)的子集;
(2)op是一个可有可无的二元判断式,被用来作为排序准则:
op(elem1,elem2)
(3)调用者必须确保在进入算法之际,两区间都应该已经按照相同的排序准则排好序了;
(4)复杂度:线性;
代码示例:
#include"fuzhu.h" using namespace std; int main() { list<int> coll; vector<int> search; INSERT_ELEMENTS(coll,1,9); PRINT_ELEMENTS(coll,"coll: "); search.push_back(3); search.push_back(5); search.push_back(7); PRINT_ELEMENTS(search,"search: "); if(includes(coll.begin(),coll.end(),search.begin(),search.end())) { cout<<"all elements of search are also in coll"<<endl; } else { cout<<"not all elements of search are also in coll"<<endl; } system("pause"); return 0; }