C# で lower_boundをListの拡張関数として実現する

先日、ABC371 D問題を回答している際に二分探索が必要になった。

概要としては、座標上の指定された区間内の総和を求める問題。
座標上の区間が与えられたとき、その区間に含まれる座標上のXiの人口Piの総和を出すのだ。

詳細な解法は公式解説に譲るとして、
①その区間に該当するXiは二分探索を実行することで両端を高速に検出
②①で検出したXiの範囲に対応するPiの総和は累積和で計算すれば高速に算出できる。

C#におけるlower_bound関数が標準関数にない

ここからはC#の標準クラスの話になるのだが、このsetクラスに当たるクラスがC#に直接実装されていないこと。
なので上記も自作の二分探索木クラスを実装して対応したりしていたのだが。

別件でListクラスのリファレンスを眺めていると、、、
あるではないか！C#で二分探索を行えるBinarySearch関数！

Listはソートされていることが条件ではあるが、List内部における二分探索木での検索が実行できる。
しかも、BinarySearchは一致する値がない場合に入力値以上を満たす最も小さいインデックスの補数を返してくれる。
つまり、C#でLowerBound関数を実装できる！

C# での実装

ということで、Listの拡張メソッドとしてLowerBoundを実装した。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AlgorithmExtend
{
    public static class BinarySearchExtensions
    {
        /// <summary>
        /// 指定された値以上を満たす要素の最小インデックスを取得する
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="cls"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        public static int LowerBound<T>(this List<T> cls, T value) 
        {
            int index = cls.BinarySearch(value);
            if (index < 0)
            {
                // 補数を戻して返却
                return Math.Abs(index + 1);
            }
            else
            {
                return index;
            }
        }

        /// <summary>
        /// 指定された値より大きいを満たす要素の最小インデックスを取得する
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="cls"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        public static int UpperBound<T>(this List<T> cls, T value)
        {
            int index = cls.BinarySearch(value);
            if (index < 0)
            {
                // 補数を戻して返却
                return Math.Abs(index + 1);
            }
            else
            {
                if (value.Equals(cls[index]))
                {
                    // 一致は含まないため次を返却する。
                    index++;
                }
                return index;
            }
        }
    }
}

問題への適用

        public static void Main()
        {
            SourceExpander.Expander.Expand();

            int N = int.Parse(Console.ReadLine());
            // setを利用して L - R 間にあるXの座標を抽出し、累積和を用いてPiの総数を計算すればよい。
            // Xi は 10^-9　～ 10^9
            long[] Xi = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long[] Pi = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
            long[] PSum = new long[Pi.Length+1];

            List<long> xList = new();
            for (int i = 0; i < Xi.Length; i++)
            {
                xList.Add(Xi[i]);
            }

            // 累積和の計算
            PSum[0] = 0;
            for (int i = 0; i < Pi.Length; i ++)
            {
                PSum[i + 1] = PSum[i] + Pi[i];
            }

            int Q = int.Parse(Console.ReadLine());
            for (int i = 0; i < Q; i++)
            {
                long ans = 0;
                long[] query = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
                // L に最も近いXiの取得
                int XLIndexBS = xList.LowerBound(query[0]);
                // R に最も近いXiの取得
                int XRIndexBS = xList.UpperBound(query[1]);
                ans = PSum[XRIndexBS] - PSum[XLIndexBS];
                Console.WriteLine(ans);
            }
        }

これでAC出たので、今度からは二分探索が必要な場合は積極的にこちらを使っていこうと思います。
※提出時はSourceExpanderを用いて拡張メソッドを読み込んでいます。