爲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

您可以使用（基於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

你可以編寫一個自定義的IComparer<int>來統計它被使用的次數，然後在你的搜索方法中使用它。 （或者爲你的線性搜索定製IEqualityComparer<int>，我想。）

Answer 3

這是一種家庭作業嗎？方法不提供這樣的信息。

如果您想要比較的數量，您必須編寫自己的IComparer二分搜索，或者仍然使用.NET方法並根據列表長度和元素位置計算計數。

Answer 4

實現一個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); 
    } 

}