Array.BinarySearch<T> メソッド (T[], T, IComparer<T>)

2013/12/12

指定した IComparer<T> ジェネリック インターフェイスを使用して、1 次元の並べ替え済み Array 全体の中から値を検索します。

Namespace:  System
アセンブリ:  mscorlib (mscorlib.dll 内)

public static int BinarySearch<T>(
	T[] array,
	T value,
	IComparer<T> comparer
)

型パラメーター

T

配列の要素の種類。

パラメーター

array
型: T []
検索対象となる、インデックス番号が 0 から始まる並べ替え済みの 1 次元 Array
value
型: T
検索するオブジェクト。
comparer
型: System.Collections.Generic.IComparer<T>
要素を比較する場合に使用する IComparer<T> 実装。
または
各要素の IComparable<T> 実装を使用する場合は null

戻り値

型: System.Int32
指定した value が存在する場合は、指定した array におけるその value のインデックス。value が見つからず、valuearray 内の 1 つ以上の要素よりも小さい場合は、負の値。これは、value より大きい最初の要素のインデックスのビットごとの補数となります。value が見つからず、valuearray 内のどの要素よりも大きい場合は、負の値。これは、最後の要素のインデックス + 1 のビットごとの補数となります。

例外条件
ArgumentNullException

arraynull です。

ArgumentException

comparernull で、value の型に array の要素との互換性がありません。

InvalidOperationException

comparernull で、valueIComparable<T> ジェネリック インターフェイスが実装されておらず、検索時に IComparable<T> ジェネリック インターフェイスが実装されていない要素が検出されます。

指定した値が Array に格納されていない場合、このメソッドは負の整数を返します。負の結果にビットごとの補数演算子 (~) を適用 (Visual Basic の場合は、負の結果と -1 を Xor 演算) して、インデックスを求めることができます。このインデックスが配列のサイズ以上の値である場合、その配列内に value より大きい要素はありません。それ以外の場合、このインデックスが、value より大きい最初の要素のインデックスになります。

比較子は、要素を比較する方法をカスタマイズします。

comparernull でない場合、array の要素は、指定した IComparer<T> ジェネリック インターフェイスの実装を使用して、指定した値と比較されます。array の要素は、comparer によって定義された並べ替え順序に基づいて、あらかじめ昇順に並べ替えられている必要があります。並べ替えが済んでいない場合は、結果が正しくない可能性があります。

comparernull の場合は、要素自体または指定した値によって提供される IComparable<T> ジェネリック インターフェイスの実装を使用して比較が行われます。array の要素は、IComparable<T> 実装によって定義された並べ替え順序に基づいて、あらかじめ昇順に並べ替えられている必要があります。並べ替えが済んでいない場合は、結果が正しくない可能性があります。

メモメモ:

comparernull で、valueIComparable<T> ジェネリック インターフェイスが実装されていない場合、検索の開始前に array の要素に IComparable<T> が実装されているかどうかテストされません。検索時に IComparable<T> が実装されていない要素が検出されると、例外がスローされます。

重複する要素を使用できます。Arrayvalue と等しい要素が複数含まれている場合、このメソッドは 1 つの要素のインデックスしか返しませんが、必ずしも該当する 1 番目の要素のインデックスとは限りません。

null は、常に他の参照型と比較できるため、null との比較によって例外が生成されることはありません。並べ替え処理では、null は、他のすべてのオブジェクトより小さいと見なされます。

メモメモ:

テストされるすべての要素について、value は適切な IComparable<T> 実装に渡されます。これは valuenull である場合も同じです。つまり、特定の要素を null と比較する方法は、IComparable<T> 実装によって決定されます。

このメソッドは、O(log n) 操作です。ここで、narrayLength です。

Sort<T>(T[], IComparer<T>) ジェネリック メソッド オーバーロードと BinarySearch<T>(T[], T, IComparer<T>) ジェネリック メソッド オーバーロードを次のコード例に示します。

コード例では、ReverseCompare という名前の文字列に対して、IComparer<string> (Visual Basic では IComparer(Of String)、Visual C++ では IComparer<String^>) ジェネリック インターフェイスを実装する代替の比較子を定義します。比較子は、CompareTo(String) メソッドを呼び出して、文字列が小さい順ではなく大きい順になるように比較対象値の順序を反転します。

配列が表示され、並べ替えられて、再表示されます。BinarySearch メソッドを使用するために配列を並べ替える必要があります。

メモメモ:

Sort<T>(T[], IComparer<T>) ジェネリック メソッドおよび BinarySearch<T>(T[], T, IComparer<T>) ジェネリック メソッドの呼び出しは、対応する非ジェネリック型の呼び出しと違いがないように見えます。これは、Visual Basic、C#、および C++ が最初の引数の型からジェネリック型パラメーターを推論するからです。

次に BinarySearch<T>(T[], T, IComparer<T>) ジェネリック メソッドのオーバーロードを使用して、2 つの文字列 (配列内に含まれない文字列と含まれる文字列) を検索します。BinarySearch<T>(T[], T, IComparer<T>) メソッドの配列と戻り値は、ShowWhere ジェネリック メソッドに渡されます。文字列が見つかるとインデックス値が表示されます。見つからなかった場合は、検索文字列が配列内に存在するときの範囲を示す要素が表示されます。文字列が配列内に存在しない場合、インデックスは負の値です。したがって、ShowWhere メソッドはビットごとの補数演算子 (C# および Visual C++ の場合は ~ 演算子、Visual Basic の場合は Xor -1) を受け取り、リスト内で検索文字列よりも大きい最初の要素のインデックスを取得します。

メモメモ:

この例を実行するには、「Windows Phone での静的 TextBlock コントロールのあるコード例のビルド」を参照してください。


using System;
using System.Collections.Generic;

public class ReverseComparer : IComparer<string>
{
   public int Compare(string x, string y)
   {
      // Compare y and x in reverse order.
      return y.CompareTo(x);
   }
}

public class Example
{
   public static void Demo(System.Windows.Controls.TextBlock outputBlock)
   {
      string[] dinosaurs = {"Pachycephalosaurus", 
                              "Amargasaurus", 
                              "Tyrannosaurus", 
                              "Mamenchisaurus", 
                              "Deinonychus", 
                              "Edmontosaurus"};

      outputBlock.Text += "\n";
      foreach (string dinosaur in dinosaurs)
      {
         outputBlock.Text += dinosaur + "\n";
      }

      ReverseComparer rc = new ReverseComparer();

      outputBlock.Text += "\nSort" + "\n";
      Array.Sort(dinosaurs, rc);

      outputBlock.Text += "\n";
      foreach (string dinosaur in dinosaurs)
      {
         outputBlock.Text += dinosaur + "\n";
      }

      outputBlock.Text += "\nBinarySearch for 'Coelophysis':" + "\n";
      int index = Array.BinarySearch(dinosaurs, "Coelophysis", rc);
      ShowWhere(outputBlock, dinosaurs, index);

      outputBlock.Text += "\nBinarySearch for 'Tyrannosaurus':" + "\n";
      index = Array.BinarySearch(dinosaurs, "Tyrannosaurus", rc);
      ShowWhere(outputBlock, dinosaurs, index);
   }

   private static void ShowWhere<T>(System.Windows.Controls.TextBlock outputBlock, T[] array, int index)
   {
      if (index < 0)
      {
         // If the index is negative, it represents the bitwise
         // complement of the next larger element in the array.
         //
         index = ~index;

         outputBlock.Text += "Not found. Sorts between: ";

         if (index == 0)
            outputBlock.Text += "beginning of array and ";
         else
            outputBlock.Text += String.Format("{0} and ", array[index - 1]);

         if (index == array.Length)
            outputBlock.Text += "end of array." + "\n";
         else
            outputBlock.Text += String.Format("{0}.", array[index]) + "\n";
      }
      else
      {
         outputBlock.Text += String.Format("Found at index {0}.", index) + "\n";
      }
   }
}

/* This code example produces the following output:

Pachycephalosaurus
Amargasaurus
Tyrannosaurus
Mamenchisaurus
Deinonychus
Edmontosaurus

Sort

Tyrannosaurus
Pachycephalosaurus
Mamenchisaurus
Edmontosaurus
Deinonychus
Amargasaurus

BinarySearch for 'Coelophysis':
Not found. Sorts between: Deinonychus and Amargasaurus.

BinarySearch for 'Tyrannosaurus':
Found at index 0.
 */


Windows Phone OS

サポート: 8.0, 7.1, 7.0

表示:
© 2015 Microsoft