5

2 つの別個のプログラム、1 つの線形検索プログラム (既に完了している)、および 2 分検索プログラムを作成するタスクがあります。これらのプログラムは、検索プロセス中に行われた比較の数もカウントする必要があります。私の線形検索プログラムは既に行われた比較の数を数えていますが、私の二分探索プログラムはそうではありません。二分探索のコードは次のようになります。

using System;
using System.Collections.Generic;

public class Example
{
public static void Main()
{

    Console.WriteLine("Input number you would like to search for");

    String Look_for = Console.ReadLine();

    int Lookfor;

    int.TryParse(Look_for, out Lookfor);

    {
        List<int> numbers = new List<int>();

        numbers.Add(1); 
        numbers.Add(2); 
        numbers.Add(3); 
        numbers.Add(4); 
        numbers.Add(5); 
        numbers.Add(6); 
        numbers.Add(7); 
        numbers.Add(8); 

        Console.WriteLine();
        foreach (int number in numbers)
        {
            Console.WriteLine(number);
        }

        int answer = numbers.BinarySearch(Lookfor);

        Console.WriteLine("The numbers was found at:");

        Console.WriteLine(answer);

    }
 }
}

比較をカウントするように変更する方法を誰かが教えてくれれば、大歓迎です。

どうもありがとう、マシュー。

4

4 に答える 4

5

IComparer<int>比較をカウントする を実装します。

private class CountComparer : IComparer<int> {

  public int Count { get; private set; }

  public CountComparer() {
    Count = 0;
  }

  public int Compare(int x, int y) {
    Count++;
    return x.CompareTo(y);
  }

}

次に、比較子を取るオーバーロードのBinarySearch比較子として使用します。

CountComparer comparer = new CountComparer();
int answer = numbers.BinarySearch(Lookfor, comparer);

次に、比較子にはカウントが含まれます。

Console.WriteLine("The binary search made {0} comparisons.", comparer.Count);

おまけ: 比較可能なタイプの一般的なカウント比較子:

private class CountComparer<T> : IComparer<T> where T : IComparable<T> {

  public int Count { get; private set; }

  public CountComparer() {
    Count = 0;
  }

  public int Compare(T x, T y) {
    Count++;
    return x.CompareTo(y);
  }

}
于 2012-10-05T08:19:51.907 に答える
3

この拡張メソッドを使用できます（この回答に基づくコード）

public static class ListEx
{
    public static Tuple<int, int> BinarySearchWithCount<T>(
        this IList<T> list, T key)
    {
        int min = 0;
        int max = list.Count - 1;
        int counter = 0;

        while (min <= max)
        {
            counter++;
            int mid = (min + max) / 2;
            int comparison = Comparer<T>.Default.Compare(list[mid], key);
            if (comparison == 0)
            {
                return new Tuple<int, int>(mid, counter);
            }
            if (comparison < 0)
            {
                min = mid + 1;
            }
            else
            {
                max = mid - 1;
            }
        }

        return new Tuple<int, int>(~min, counter);
    }
}

//Which returns a tuple with the item and a number of comparisons. 
//Here is how you can use it:

class Program
{
    static void Main(string[] args)
    {
        var numbers = new List<int>();
        numbers.AddRange(Enumerable.Range(0, 100000));

        var answer = numbers.BinarySearchWithCount(2);
        Console.WriteLine("item: " + answer.Item1);   // item: 2
        Console.WriteLine("count: " + answer.Item2);  // count: 15

    }
}
于 2012-10-05T08:39:30.097 に答える
3

IComparer<int>使用回数をカウントするカスタムを作成し、これを検索メソッドで使用できます。（または、線形検索のカスタムIEqualityComparer<int>だと思います。）

于 2012-10-05T08:17:47.580 に答える
0

これはある種の宿題ですか？メソッドはそのList<T>.BinarySearchような情報を提供しません。

比較の数が必要な場合は、独自のIComparerバイナリ検索を作成するか、.NET メソッドを使用して、リストの長さと要素の位置からカウントを計算する必要があります。

于 2012-10-05T08:19:15.803 に答える