【C#】BinarySearchで指定した要素がなかった場合の処理

C#で、BinarySearchを使用して検索をかけた時、指定した要素がなかった時の処理についてのメモです。

今回もAtCoderで必要になった処理です。

atcoder.jp

BinarySearchの使い方

0-10の偶数を+0をリストに格納します。そのリストに対してBinarySearchで検索をかけます。まずは、

List<int> list = new List<int>();
for (int i = 0; i < 10; i += 2)
{
    list.Add(i);
}
Console.WriteLine(string.Join(" ", list));
Console.WriteLine("-------");
Console.WriteLine("BinarySearch(0)  " + list.BinarySearch(0));
Console.WriteLine("BinarySearch(1)  " + list.BinarySearch(1));
Console.WriteLine("BinarySearch(2)  " + list.BinarySearch(2));
Console.WriteLine("BinarySearch(3)  " + list.BinarySearch(3));
Console.WriteLine("BinarySearch(4)  " + list.BinarySearch(4));

出力結果

0 2 4 6 8
-------
BinarySearch(0)  0
BinarySearch(1)  -2
BinarySearch(2)  1
BinarySearch(3)  -3
BinarySearch(4)  2

指定した要素のインデックスを返します。要素がないと負の値を返します。

チルダ(~)を使う

補数演算子としての”~”を使うと、”指定した要素がない場合、していした要素より大きい最初の要素のインデックス番号”を返します。

Console.WriteLine("-------");
Console.WriteLine("BinarySearch(0)  " + list.BinarySearch(0));
Console.WriteLine("~BinarySearch(1)  " + ~list.BinarySearch(1));
Console.WriteLine("BinarySearch(2)  " + list.BinarySearch(2));
Console.WriteLine("~BinarySearch(3)  " + ~list.BinarySearch(3));
Console.WriteLine("BinarySearch(4)  " + list.BinarySearch(4));

このようにな出力結果になります。

BinarySearch(0)  0
~BinarySearch(1)  1 // 1はリストにないので、2のインデックスを返しています。
BinarySearch(2)  1
~BinarySearch(3)  2 // 上記と同様です。
BinarySearch(4)  2

この性質を利用して、ABC138を解くことができます。