Count the number of comparisons made for BinarySearch

Question

I have the task of creating two separate programs, one linear search program that I have already completed, and a binary search program. These programs should also take into account the number of comparisons performed during the search process. My linear search program already counts the number of comparisons made while my binary search program cannot. The code for binary search is as follows:

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 anyone can tell me how to change it to count comparisons, it would be quite helpful.

Thanks a lot, Matthew.

Answer 1

You can use this extension method (code based on this answer )

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

Answer 2

Implement IComparer<int> , which allows for 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 a comparator in the BinarySearch overload, which takes a comparator :

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

Then the comparator contains a counter:

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

---

Bonus: general counting correlator 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); } } 

Answer 3

You can write a custom IComparer<int> that counts the number of times it is used, and then use this in your search methods. (Or a custom IEqualityComparer<int> for your linear search, I suppose.)

Answer 4

Is this some kind of homework? The List<T>.BinarySearch does not provide such information.

If you need the number of comparisons, you need to either write your own binary search IComparer , or use the .NET method, and calculate the counts from the length of the list and the position of the element.