【C#】BinarySearchで指定した要素がなかった場合の処理
C#で、BinarySearchを使用して検索をかけた時、指定した要素がなかった時の処理についてのメモです。
今回もAtCoderで必要になった処理です。
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を解くことができます。