鉄則本 A11 - Binary Search 1 (★2)

ここでは、lower_bound() を使って解いてみることにする。

• 問題へのリンク

問題概要

小さい順に並べられた配列 が与えられる。

値 が の中で何番目の要素の値であるかを求めよ。ただし、 の中に値 の要素は含まれているとする。

制約

• 

考えたこと

実は単純な for 文でも解ける。鉄則本では二分探索を用いて実装してほしいとしている。

ここでは、二分探索を実装した C++ の標準関数 lower_bound() を使うこととした。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, X;
    cin >> N >> X;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    int res = lower_bound(A.begin(), A.end(), X) - A.begin();
    cout << res+1 << endl;
}