二分ルックアップコード実装

機能:長さnの配列で、この配列の値の位置をクエリーします.
時間複雑度:log 2(n)
次のアルゴリズムは、秩序配列(昇順)に使用され、[left,right)範囲内の最後のeに等しい数以下の下付き記号を返すべきである.
EG:  b[5] = {1, 2, 3, 3, 5};    find(0, 5, 3) = 4 
はいれつ

int find(int left,int right, ll e) {
    int mid;
    while(left < right) {
        mid = (left+right)/2;
        (e < b[mid]) ? right = mid : left = mid + 1; //    b[]      ，           
    }
    return left-1;
}

1つの問題で検証します.
タイトルリンク:転送ゲート
参照コード:

#include 
#include 
using namespace std;
typedef long long ll;
const int N = 200100;
ll a[N];
ll b[N];
int find(int left,int right, ll e) {
    int mid;
    ++right;
    while(left < right) {
        mid = (left+right)/2;
        (e < b[mid]) ? right = mid : left = mid + 1;
    }
    return left-1;
}
int main()
{
    int n, m;
    ll sum = 0;
    cin >> n >> m;
    b[0] = 0;

    for(int i=1;  i<=n; ++i) {
        scanf("%I64d", &a[i]);
        sum += a[i];
        b[i] = a[i] + b[i-1];
    }

    ll now = 0, temp;
    int cnt = 0;

    for(int i=1; i<=m; ++i) {
        scanf("%I64d", &temp);
        now += temp;

        if(now >= sum) {
            cout << n << endl;
            now = 0;
            continue;
        }

        cnt = find(0, n, now);
        if(b[cnt] - now > 0)
            cout << n-cnt+1 << endl;
        else
            cout << n-cnt << endl;
    }
    return 0;
}