STL之binary_search

概括
大家都知道,二分查找是在排序后的基础上来对其进行查找操作。所以在使用bianry_search的时候,需要将要查找的容器进行排序。
说明
在这里说明两种,一种是对结构体的二分操作,一种是对数组进行二分操作,在操作之前,肯定是需要对结构体进行排序,如何排序,这里就用到了STL里面很实用的sort函数。
特别强调:排序的必须是从小到大
vector
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> V;
int main()
{
    V.push_back(2);
    V.push_back(3);
    V.push_back(1);
    sort(V.begin(), V.end());//对vector 的排序
    if(binary_search(V.begin(), V.end(), 2)) // 对vector进行二分查找
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

struct
对结构体进行二分操作之前,肯定需要先对其排序。对结构体排序需要用到运算符重载,对结构体中的<进行重载,排序可以直接用sort排序,或者是定义一个结构体类型的set,set会对其去重排序,然后就可以使用二分查找了。
struct Node//结构体定义以及运算符重载
{
    int x,y;
    bool operator<(const Node &rhs)const
    {
        if(x == rhs.x)
            return y < rhs.y;
        else
            return x < rhs.x;
    }
};
//二分查找函数
if(binary_search(nodes,nodes+n,tmp))
    cout << "Yes" << endl;
else
    cout << "No" << endl;
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐