BinarySearch (一)

在 .Net 的 Array 物件，有個 BinarySearch 方法，光從字面上猜，應該是用來「找查」用的。 於是寫了一段 code 來試試。

string strInput = "paladin,hugo,ken,keen,polly,panda,lillian,gemma,hana";
string[] strArray = strInput.Split(',');

foreach (string s in strArray)
{
      Console.WriteLine(s);
}

int iLocation=Array.BinarySearch(strArray, "panda");
Console.WriteLine("Index of 'panda' is :"+iLocation.ToString());
Console.Read();

蠻不給面子的，竟然沒用！
後來發現，要使用 BinarySearch( )，必須要先將資料進行排序才行，也就是說，不排序，就不給用。而在 Array 物件，他也同時提供了 Sort( )方法，正是使用 BinarySearch( ) 所需要的。於是修改了一下上面的程式，加上 Array.Sort(strArray) 。

string strInput = "paladin,hugo,ken,keen,polly,panda,lillian,gemma,hana";
string[] strArray = strInput.Split(',');
Array.Sort(strArray);

foreach (string s in strArray)
{
      Console.WriteLine(s);
}

int iLocation=Array.BinarySearch(strArray, "panda");
Console.WriteLine("Index of 'panda' is :"+iLocation.ToString());
Console.Read();

的確，加上排序後，查詢的功能就正確了。但這時心裡頭不免偷偷地「暗」一下微軟，幹麼不乾脆一點，還要讓人這麼麻煩。後來發現，其實這是有原因的。Binary Search (二分搜尋法)，是用來搜尋已經排序過的資料。基本上，是先將要比較的資料與所有資料的中間值作比較，根據比較結果的大、小或相等，再來決定下一個搜尋範圍或直接得到搜尋結果。而這種搜尋方式，當然會比我們寫一個迴圈從第一筆慢慢找到最後一筆還來的快許多。

然而，別忘了使用 BinarySearch ( ) 的前提是必須先將資料排序，所以必須將排序所花的時間與搜尋時間加在一起才公平。在效能上來說，如果你要查詢的陣列只有使用一次而已，循序搜尋也不見得會比較慢，因為當資料量很龐大時，光排序也需要花不少時間。相反地，如果你的陣列會一直不斷的被重複使用，只要事先執行一次排序，之後就只需不斷地呼叫 BinarySearch( )則會較佔優勢，這正也是為何自己先前質疑使用 BinarySearch( ) 為何要與 Sort( ) 分開的原因。