B11 - Binary Search 2

atcoder.jp

LowerBound が標準ライブラリには見当たらなかったので自前実装。

var N = int.Parse(Console.ReadLine()!);
var A = Console.ReadLine()!.Split(" ").Select(int.Parse).ToList();
var Q = int.Parse(Console.ReadLine()!);
var X = new List<int>();
for (var i = 0; i < Q; i++)
{
    X.Add(int.Parse(Console.ReadLine()!));
}

var sortedA = A.Order().ToList();
for (var i = 0; i < Q; i++)
{
    var idx = LowerBound(sortedA, X[i]);
    Console.WriteLine(idx);
}

static int LowerBound(IReadOnlyList<int> A, int X)
{
    if (A.Count == 0) return -1;
    if (A[0] > X) return 0;

    var L = 0;
    var R = A.Count;
    while ((R - L) > 1)
    {
        var M = (L + R) / 2;
        if (A[M] < X)
        {
            L = M;
        }
        else
        {
            R = M;
        }
    }
    return R;
}