lower-bound 自己实现

// https://vjudge.net/problem/HackerRank-cpp-lower-bound

大致题意和这个差不多

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=100000+10;

int a[maxn];

int n;

int q;

int my_lower_bound(int x)

{

    int lb=-1, ub=n;//ub要赋值为n，因为可能不存在，所有a[i]都小于x

    while(ub-lb>1)

    {

        int mid = (lb+ub)/2;

        if(a[mid] >= x)

            ub=mid; // (lb, mid]

        else

            lb=mid; // (mid, ub]

    }

    return ub;

}

int main()

{

    cin>>n;

    for(int i=0;i<n;i++)

        cin>>a[i];

    cin>>q;

    for(int i=0;i<q;i++)

    {

        int x;

        cin>>x;

        int ans = my_lower_bound(x);

        if(a[ans]!=x)

        {

            cout<<"No "<<ans+1<<endl;

        }

        else

        {

            cout<<"Yes "<<ans+1<<endl;

        }

    }

    return 0;

}