這是一個相當有趣的題目，前面講了 Binary search，因為它利用資料已排序好的特性，所以每次在尋找時可以中候選資料的中間切入來尋找，所以它的 Big O 該如何評估呢 ?
我們之前講到，如果現在找資料的方法是一個一個找，也就是說有十個資料時，最多要找十次，有十萬個資料時，最多要找十萬次，因此我們知道這方法和輸入的資料量成正比，所以是 O(n)．
Binary search 的 Big O 顯然一定比 O(n) 要快，那到底有多快呢 ? 我們可以來觀察一下．每次 binary search 在進行尋找時會從候選資料的中間尋找，然後依照目標值的大小來決定下一次尋找的候選資料是在前面一半還是後面一半，所以每次尋找後都可以將一半的資料給排除，比如說一開始有 100 個資料，經過第一次尋找後，下一回的候選資料就變成 50 個，再下一個就變成 25 個，以此類推．用數學的角度來看就形成了 2y = n，其中 n 是資料輸入量，而 y 是尋找的次數，把式子轉變一下就形成了 y = log(n) ，其中這個 log 不是以 10 為基底，是以 2 為基底．所以，Binary search 的 Big O 就是 O(log(n))．
未來，寫程式的時候，如果你發現你的資料已排序好，那就記得多利用 Binary search 來做資料尋找，而不要一個一個找．因此，你也知道 O(log(n)) 的程式是比 O(n) 的程式還要來的快．
一般來說，寫 Binary search 有兩種寫法，一種是 recursive，另一種是 iterative.
Recursive :
bool BSearch(int[] A, int target, int start, int end)
{
if (start < end) return false;
int mid = (start + end) / 2;
if (A[mid] == target)
return true;
else if (target > A[mid])
return BSearch(A, target, mid + 1, end);
else
return BSearch(A, target, start, mid - 1);
}
Iterative :
bool BSearch(int[] A, int target)
{
int start = 0;
int end = A.Length - 1;
while (start < end)
{
int mid = (start + end) / 2;
if (A[mid] == target)
return true;
else if (target > A[mid])
start = mid + 1;
else
end = mid - 1;
}
return false;
}
在沒有其他特別條件限制的情況下，Iterative 的寫法比較容易懂也比較好維護，同時也能避免 stack overflow (未來文章會再介紹) 的問題，所以多建議使用 Iterative 的寫法．
