题解 | 【模板】二分

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
//方法一：直接使用内置的函数
//方法二：自己实现二分查找
vector<int>::iterator bisearch(vector<int>::iterator left,vector<int>::iterator right,int target)//返回数组范围中第一个大于等于target的位置的迭代器
{
    //找中间值，随机访问迭代器支持直接算术运算
    while(left<right)
    {
        auto mid=left+(right-1-left)/2;
        if(*mid<target)
            left=mid+1;
        else
            right=mid;
    }
    //处理区间[left,right);其中在left左边的元素都小于target，
    //right自身和其右边的元素都大于等于target    
    return right;
}

vector<int>::iterator bisearch1(vector<int>::iterator left,vector<int>::iterator right,int target)//返回数组范围中第一个大于target的位置的迭代器
{
    //找中间值，随机访问迭代器支持直接算术运算
    while(left<right)
    {
        auto mid=left+(right-1-left)/2;
        if(*mid<=target)
            left=mid+1;
        else
            right=mid;
    }
    //处理区间[left,right);其中在left左边的元素都小于等于target，
    //right自身和其右边的元素都大于target    
    return right;
}

int main() {
    int n, q;
    cin >> n >> q;
    vector<int>nums;
    while (n--)
    {
        int num;
        cin >> num;
        nums.push_back(num);
    }
    //依次处理询问
    int op, l, r, x;
    while (cin >> op >> l >> r >> x)
    {
        auto begin = nums.begin() + l;
        auto end = nums.begin() + r;
        if (op == 1)//情况一
        {
            auto it = bisearch(begin, end, x);
            if (it != end)
                cout<< *it<<endl;
            else
                cout<< -1<<endl;
        }
        //情况二
        else if (op == 2)
        {
            auto it = bisearch1(begin, end, x);
            if (it != end)
                cout << *it<<endl;
            else
                cout << -1<<endl;
        }
        //情况三
        else if (op == 3)
        {
            auto it = bisearch(begin, end, x);
            if (it != begin)
                cout << *(--it)<<endl;
            else
                cout << -1<<endl;
		}
        //情况四
        else if (op == 4)
        {
            auto it = bisearch1(begin, end, x);
            if (it != begin)
                cout << *(--it)<<endl;
            else
                cout << -1<<endl;
		}
    }
	return 0;
}