Count number of comparisons made for BinarySearch

Question

I have the task of creating two seperate programs, one linear search program, which I have already completed, and a binary search program. These programs must also count the number of comparisons made during the search process. My linear search program already counts the number of comparisons made while my binary search program cannot. The code for the binary search looks like this:

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

    }
 }
}

If anybody can tell me how to modify it to count comparisons it would be greatly appreciated.

Many thanks, Matthew.

Answer 1

Implement an IComparer<int> that counts the comparisons:

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

}

Then use it as comparer in the overload of BinarySearch that takes a comparer:

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

The comparer then contains the count:

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

---

Bonus: A generic counting comparer for any comparable type:

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

}