C++库函数 使用dinary

dinary_search二分查找,查找给定容器中是否包含第三个参数，函数原型如下：

bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val);

第一个参数是需要遍历的容器中的第一个元素的迭代器值，第二个参数是容器中最后一个元素之后的迭代器值，需要遍历整个容器第一个参数给到  (容器对象).begin（）  第二个参数给到 （容器对象）.end() 。 第三个参数则需要向容器查找的值。

返回值是bool值 找到则返回 true 反之返回 false。

     例如：

vector vec = {1,2,3,4};

bool bol = binary_search(vec.begin(), vec.end(), 4);

cout.setf(ios::boolalpha);

cout << bol << endl;

binary_search默认给到查询条件是 仿函数less(), 如果给定容器元素没有按照less() 规则排序（比如:容器中的前一个元素值必须小于后一个元素值,也即升序排序），那么我们可能会找不到其中的值。

   例如：

vector vec = {1,4,2,3,};

bool bol = binary_search(vec.begin(), vec.end(), 4);

cout.setf(ios::boolalpha);

cout << bol << endl;

但是我们需要在容器中查找val的时候，并不一定需要按照升序排序。因为binary_search是二分查找（而需要在容器中查找的值val恰好在这个容器的任意一个地方），所以给定三个参数如果是在 index=1+（容器元素个数的一半），index个参数之后，那么第index个参数必须比val 要小，接下来容器查找的索引会变成 index2 =index+1+((容器元素个数-index)/2),如果val还在这个index2个元素之后那么 第index2个元素也要比val要小，然后容器查找的索引为 index3 = index2+1+（容器-index2）/2, 如果val还在index3之后，这个规则如此简单，想必，查看本文章的各位应该很容易就搞清了吧。那如果val 不在某个index之后呢，它恰好比index之后，又在index2之前。那么第index2个元素就必须要比val值要大，这是必须的不然binary_search还会继续找下去，直到 index到达容器末尾，当val在容器的位置恰好在index和index2之间，那么下一个index3 = index+1+（（容器元素大小-index）/2）/2（至于为什么是（容器元素大小-index）/2,详解可能会很麻烦），那么还需要判断val容器中第index3处元素和index2处的元素之间，或在index处元素和index3处元素之间，如果是前一种那么index3处的元素就要比val要小，此时index4 = index3+1+（（容器元素大小-index）/2-（（容器元素大小-index）/2）/2+1），如果（（容器元素大小-index）/2-（（容器元素大小-index）/2）/2+1）是一个0（int），Index4处的元素是最后一次比较的元素，我刚刚说了index3处的元素是要比val要小的，那么index4很有可能就是我们要查找的val，或者index4+1处的元素就是val，如果是后一种index4必须要比val要小，否则找不到正确的值，函数返回false。

刚刚我举例了index =1+（容器元素个数/2），val在index之后。现在我们看看val在index之前而容器内元素不规则排序而val又在容器的某一处位置，需要什么条件才能找到val。如果val在index之前那么index处的元素必须要比val要大，下一次index2 = 1+（容器元素个数/2）/2，如果val在index之后，那么index要比val要小下一次index3 = index2+1+(容器元素个数/2 - (容器元素个数/2)/2 +1)/2 ，如果val还在Index3处元素之后，index3处的元素肯定要比val要小，假设下一次索引为最后一次比较那么index4 = index3 +1 +0; 如果index4处的索引要比val小而val在容器中的话，那么index5 =index4+1 ，index5处的元素就是val，同时index5 == index； 不然index4就是val所在的位置。还有很过例子，我举的例子是在容器数量为8个的时候，用binary_search查找无序规则容器的条件，任何一种条件不满足，而val只在容器中存在一次，那么一定找不到。

binary_search的重载版本

bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Pr _Pred)

我们可以指定binary_search查找的条件，比如greater() 它和less<>()的规则正好相反，又比如我们使用binary_search原版，它要求容器升序排序，如果我给一个降序排序的容器给它，它一定找不到容器中的任何一个元素。

例如：

vector vec = { 4,3,2,1 };

bool bol = binary_search(vec.begin(), vec.end(), 4);

cout.setf(ios::boolalpha);

cout << bol << endl;

 此时我再将greater()作为第四个参数，结果就不一样了。

vector vec = { 4,3,2,1 };

bool bol = binary_search(vec.begin(), vec.end(), 4);

cout.setf(ios::boolalpha);

cout << bol << endl;

bol = binary_search(vec.begin(), vec.end(), 4,greater());

cout << bol << endl;