C#のList/Arrayでlower_bound/upper_bound

ソース

public class lower_bound<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return 0 <= x.CompareTo(y) ? 1 : -1;
    }
}
public class upper_bound<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return 0 < x.CompareTo(y) ? 1 : -1;
    }
}

使い方&結果

var l = new List<int>() { 1, 1, 2, 2, 3, 3, 5, 6, 6 };
for(var i=0;i<=7;++i)
{
    var lb = l.BinarySearch(i, new lower_bound<int>());
    var ub = l.BinarySearch(i, new upper_bound<int>());
    Console.WriteLine($"Search {i}");
    Console.WriteLine($"lb:{lb},{~lb} - ub:{ub},{~ub}");
}
Search 0
lb:-1,0 - ub:-1,0
Search 1
lb:-1,0 - ub:-3,2
Search 2
lb:-3,2 - ub:-5,4
Search 3
lb:-5,4 - ub:-7,6
Search 4
lb:-7,6 - ub:-7,6
Search 5
lb:-7,6 - ub:-8,7
Search 6
lb:-8,7 - ub:-10,9
Search 7
lb:-10,9 - ub:-10,9

マッチさせないことでlower_boud/upper_boundをひねり出してるので結果に~が要ります。

docs.microsoft.com

降順に対してもちょっと変更すれば使えます。

public class desc_lower_bound<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return 0 <= y.CompareTo(x) ? 1 : -1;
    }
}
public class desc_upper_bound<T> : IComparer<T> where T : IComparable<T>
{
    public int Compare(T x, T y)
    {
        return 0 < y.CompareTo(x) ? 1 : -1;
    }
}
var l = new List<int>() { 6, 6, 5, 3, 3, 2, 2, 1, 1 };
for(var i=0;i<=7;++i)
{
    var dlb = l.BinarySearch(i, new desc_lower_bound<int>());
    var dub = l.BinarySearch(i, new desc_upper_bound<int>());
    Console.WriteLine($"Search {i}");
    Console.WriteLine($"dlb:{dlb},{~dlb} - dub:{dub},{~dub}");
}
Search 0
dlb:-10,9 - dub:-10,9
Search 1
dlb:-8,7 - dub:-10,9
Search 2
dlb:-6,5 - dub:-8,7
Search 3
dlb:-4,3 - dub:-6,5
Search 4
dlb:-4,3 - dub:-4,3
Search 5
dlb:-3,2 - dub:-4,3
Search 6
dlb:-1,0 - dub:-3,2
Search 7
dlb:-1,0 - dub:-1,0

計算量は測ってないけどO(log n)。ソース見たら普通の二分探索だし。

referencesource.microsoft.com

参考

jpliterature.hatenablog.com

背景

競プロやってるとupper_boudやlower_bound使いたくなりませんか？なりますよね？なりました。