利用List或者數(shù)組存儲數(shù)據(jù)，希望以此改善你的程序，可以對List或者數(shù)組的BinarySearch方法進(jìn)行評估。如果是一個可變數(shù)量的元素集合，Binary搜索是針對集合中的值進(jìn)行排序的一種“令人吃驚的”算法，其算法復(fù)雜度為O(log n)，與C#中其它排序方法相比，它具備更高的效率。

　　示例：

　　下面是一個對List類型使用BinarySearch方法的示例。你必須為List中所使用的類型提供一個值，這樣該方法才能通過編譯。程序中通常使用字符串，這里也就使用string類型。

BinarySearch方法示例代碼：

 1 using System;
 2  using System.Collections.Generic;
 3 
 4  class Program
 5 {
 6     static void Main()
 7     {
 8         List<string> l = new List<string>();
 9         l.Add("acorn");      // 0
10          l.Add("apple");      // 1
11          l.Add("banana");     // 2
12          l.Add("cantaloupe"); // 3
13          l.Add("lettuce");    // 4
14          l.Add("onion");      // 5
15          l.Add("peach");      // 6
16          l.Add("pepper");     // 7
17          l.Add("squash");     // 8
18          l.Add("tangerine");  // 9
19 
20         // This returns the index of "peach".
21          int i = l.BinarySearch("peach");
22         Console.WriteLine(i);
23 
24         // This returns the index of "banana".
25          i = l.BinarySearch("banana");
26         Console.WriteLine(i);
27 
28         // This returns the index of "apple".
29          i = l.BinarySearch("apple");
30         Console.WriteLine(i);
31 
32         Console.ReadKey();
33     }
34 }

輸出：

6
2
1

　　描述。上述程序從List中找出了“peach”、“banana”，和“apple”這三個字符串的位置的值。注意List中的項是按照字母順序排列的。如果List或者數(shù)組沒有經(jīng)過排序，使用BinarySearch方法將會得不到正確結(jié)果。至于是按照數(shù)值大小、字母順序，或者ASCII來排序，都是可以的。

　　比較基準(zhǔn)

　　在針對一個較大的集合進(jìn)行搜索時，binary搜索比linear搜索的效率要高很多，對于元素個數(shù)小于100的集合，BinarySearch較慢，可能是執(zhí)行時的資源消耗導(dǎo)致的。

　　理解BinarySearch

　 　我們注意到Wikipedia對binary搜索的陳述：“makes progressively better guesses, and closes in on the location of the sought value by selecting the middle element in the pan.”參見Wikipedia的文章“Binary Search Algorithm”。MSDN對List的BinarySearch方法作了如下陳述：“返回元素基于0的索引值”。然而，必須使用一個排序過的List。

　　字典是什么？

　　這里我們提到字典是恒定的查找時間哈希表。對于我所用到的數(shù)據(jù)，不管List采用哪種排序算法都沒有字典高效快速。一個顯然的情況是，你必須為大多數(shù)的方案挑選字典。參見上述比較基準(zhǔn)，隨著集合元素的增加，BinarySearch方法比linear搜索更高效。

　　對于非常較大的集合，比如有著上百萬的元素，建立起一個字典將會消耗掉由查找操作所節(jié)省下來的時間。然而，我發(fā)現(xiàn)這種情況并不常見。

　　總結(jié)

　　這篇文章講述了在什么樣的情況下可以使用List類型的BinarySearch方法。針對大集合，BinarySearch使用了一個比迭代 搜索更好的算法，但是對于小集合，其效率又通常低于字典。我建議你在每一次考慮BinarySearch方法時做一個性能監(jiān)測。你可以從Array.BinarySearch方法這篇文章中了解.NET Framework內(nèi)部的Array.BinarySearch的信息。