這幾天看一下資料庫索引(index)的問題，了解到B-Tree及Binary Search Tree（二元搜尋樹），就必須了解什麼是Binary Search（二元搜索法），不過對非資工本科的我來說真是燒腦，這邊僅記錄我的理解，可能有錯歡迎指正。
我對於時間複雜度(Time Complexity)仍處在幼稚園階段，所以對於Binary Search的時間複雜度為什麼是對數時間O(log(n))以及O(log(n))所代表的意義感到很疑惑。
Binary Search根據維基百科的說明：
Binary Search是一種在有序陣列中尋找某一特定元素的搜尋演算法。搜尋過程從陣列的中間元素開始，如果中間元素正好是要尋找的元素，則搜尋過程結束；如果某一特定元素大於或者小於中間元素，則在陣列大於或小於中間元素的那一半中尋找，而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列為空，則代表找不到。這種搜尋演算法每一次比較都使搜尋範圍縮小一半。
所以Binary Search是一種用來從一個有排序的(sorted)陣列中尋找特定元素的演算法，範例如下。
有一個排序的陣列如下
+---+---+---+---+----+----+----+----+----+----+----+----+----+----+----+----+
| 1 | 3 | 5 | 8 | 12 | 13 | 15 | 16 | 18 | 20 | 22 | 30 | 40 | 50 | 55 | 67 |
+---+---+---+---+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
^
如果今天要找的是元素13，以Binary Search搜尋先從陣列中間的數16開始比對（18也可以，不過範例會以最糟的情況來看），因為13 < 16，所以折半搜尋較小的那一半，折半後如下
+---+---+---+---+----+----+----+----+
| 1 | 3 | 5 | 8 | 12 | 13 | 15 | 16 |
+---+---+---+---+----+----+----+----+
0 1 2 3 4 5 6 7
^
接著再和中間的數8比，因為13 < 8，所以折半搜尋較大的那一半，折半後如下
+----+----+----+----+
| 12 | 13 | 15 | 16 |
+----+----+----+----+
^
接著和中間的數15比，因為13 < 15，所以折半搜尋較小的那一半，折半後如下
+----+----+
| 12 | 13 |
+----+----+
^
接著和中間的數12比，因為13 > 12，所以折半搜尋較大的那一半，折半後最後只剩13
+----+
| 13 |
+----+
^
以上一共比了4次才找到要找的13，折半(1/2)的次數是4次，也就是1/2 * 1/2 * 1/2 * 1/2 = (1/2)4。
所以從16個元素的陣列中找到某一元素可寫成
16 * (1/2)4 = 1
假設今天陣列有n個元素，則以上可改寫為
n * (1/2)k = 1
上面的算式等於
n * (1k/2k) = 1，也就是n * 1/2k = 1
左右兩邊同乘上2^k，則為
2k * n/2k = 2k
n = 2k
所以以2為底n的對數是log2(n) = k，所以k就是log2(n)，也就是在最糟情況下，要從n個元素中搜尋到某一個元素，則要折半比對的次數為k次，也就是log2(n)次。
如果今天n = 64，則k = log2(64)等於6；如果n = 128則k = log2(128)等於7，可以看到元素越多，搜尋的次數雖然也是會越多次，但次數增長的速度趨緩。
至於O(log(n))的O稱作大O符號(Big-O notation)，又稱為漸進符號，代表演算法時間函式的上限(Upper bound)，也就是在最壞的狀況下，演算法的執行時間不會超過O(log(n))。
所以O(log(n))的時間複雜度簡單來說就是，當規模(n)增大時，所花的時間會以對數時間增加，也就是時間成長率會隨著規模增加而遞減。
Binary Search在日常生活的應用很多，例如男生在看迷片時，通常會想直接跳到精彩片段，在播放器沒有預覽功能的情況下，此時Binary Search就可以派上用場了，例如60分鐘的片，就先跳到30分的位置，並依照上面的方法依序尋找，很快就可以跳到想看的片段了。
在Java中搜尋已排序陣列中特定的值時，也可以利用binary search來提升效能。
3 則留言:
Very concise and clear explanation
you bet
13 > 8
張貼留言