c# - 计算为 BinarySearch 进行的比较次数

Question

我的任务是创建两个单独的程序，一个线性搜索程序(我已经完成)和一个二进制搜索程序。这些程序还必须计算在搜索过程中进行的比较次数。我的线性搜索程序已经计算出比较次数，而我的二分搜索程序则不能。二进制搜索的代码如下所示:

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);

    }
 }
}

如果有人能告诉我如何修改它来计算比较，将不胜感激。

非常感谢，马修。

Answer 1

实现 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);
  }

}

然后将其用作the overload of BinarySearch that takes a comparer中的比较器:

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);
  }

}