バイナリサーチの結果の最初のインデックスを取得するには？

Question

私はいくつか問題があります。

List<int> firstList = new List<int> { 1, 2, 2, 3, 5}; 

List<int> secondList = new List<int> { 2, 3, 1 }; 

⇒真の結果は次のとおりです：{1, 3, 0}

私はfirstListに存在するsecondList内の番号の最初のインデックスを取得したいと思い、私は、次のような2リストを持っています。 list.BinarySearch()を使用しましたが、結果は{2, 3, 0}でした。

Answer 1

List<int> firstList = new List<int> { 1, 2, 2, 3, 5}; 
    List<int> secondList = new List<int> { 2, 3, 1 }; 

    var output = secondList.Select(item => firstList.IndexOf(item)); // [1 , 3 , 0] 

あなたはBinarySearchロジックとIndexOfを置き換えることができますが、BinarySearchはあなたが最低の番号を取得することはできませんので、IndexOfメソッドは、最低のマッチング・インデックスを返しません、最初に一致した要素のインデックスを返します。

Answer 2

反復二番目の配列を通って、最初の配列の要素のインデックスを取得：

foreach (int item in secondList) 
{ 
    Console.WriteLine(firstList.IndexOf(item)); 
} 

Answer 3

問題は、リストには、あなたのケースのように重複する値が含まれている場合、BinarySearch方法のいずれかのインデックスを返すということです一致する値（非決定論的）。

望ましい結果を得るために、あなたは、このようなカスタム拡張メソッドを作成し、使用することができます：あなたは大きなfirstListを持っているので、あなたがする必要がある場合

var result = secondList.Select(x => firstList.BinarySearchFirst(x)).ToList(); 
// { 1, 3, 0 } 

Answer 4

：

public static class ListExtensions 
{ 
    public static int BinarySearchFirst<T>(this List<T> source, T item, IComparer<T> comparer = null) 
    { 
     if (comparer == null) comparer = Comparer<T>.Default; 
     int index = source.BinarySearch(item, comparer); 
     while (index > 0 && comparer.Compare(source[index], source[index - 1]) == 0) 
      index--; 
     return index; 
    } 
} 

使用例をBinarySearchを試してくださいを改訂してください：BinarySearchによって、が保証されていないであることを確認し、その後、左側に移動してくださいヴィングは、同じ項目をお読みください。

List<int> firstList = new List<int> { 1, 2, 2, 3, 5 }; 

    List<int> secondList = new List<int> { 2, 3, 1, 123 }; 

    var result = secondList 
    .Select(item => firstList.BinarySearch(item)) 
    .Select(index => index < 0 ? -1 : Enumerable 
     .Range(0, index + 1)  // we have to scan [0..index] at the worst case 
     .Select(i => index - i) // scan in reverse 
     .TakeWhile(i => firstList[index] == firstList[i]) // take while items are the same 
     .Last()); // finally, we want the last item 

テスト

// 1, 3, 0, -1 
    Console.Write(String.Join(", ", result)); 

Answer 5

C++は、このための標準ライブラリ関数は、ここではC＃実装だlower_bound().

を呼びかけています。あなたが大規模なコレクションを検索する場合に便利です：戻りません-1それが見つからない要素のために、私たちはそうのようにそれをラップすることができますことを修正するために

public static int LowerBound<T>(IList<T> values, T target, int first, int last) 
    where T : IComparable<T> 
{ 
    int left = first; 
    int right = last; 

    while (left < right) 
    { 
     int mid = left + (right - left)/2; 
     var middle = values[mid]; 

     if (middle.CompareTo(target) < 0) 
      left = mid + 1; 
     else 
      right = mid; 
    } 

    return left; 
} 

：

public static int LowerBoundOrMinusOne<T>(IList<T> values, T target, int first, int last) 
    where T : IComparable<T> 
{ 
    int result = LowerBound(values, target, first, last); 

    if (result >= last || result < first || values[result].CompareTo(target) != 0) 
     return -1; 

    return result; 
} 

ここ

は、あなたがそれを使用する方法です。もちろん

List<int> firstList = new List<int> { 1, 2, 2, 3, 5 }; 
List<int> secondList = new List<int> { 2, 3, 1 }; 

List<int> result = secondList 
    .Select(value => LowerBoundOrMinusOne(firstList, value, 0, firstList.Count)) 
    .ToList(); 

Console.WriteLine(string.Join(", ", result)); 

それはO（LOG2（N））ではなくO（N）の複雑さを持っているので、これは主に大規模なリストへの利益のです。