Algorithms筆記12 - Binary search using D&C strategy

Binary Search

Binary search是一個divide and conquer algorithm:

binary search將一個problem分成兩個等分的subproblem，由於input是sorted array，所以每次都能刪除一個不可能得到答案的subproblem，等於每次problem size變成一半：

最後的combine所有subproblem的答案時，那些被捨棄掉的subproblem是空集合，所以最後一個subproblem中找到（或確定沒找到）的index就是整個母問題的解。

Worst-case Running time analysis

binary search最差的結果就是找不到這個數的index，如果寫成recurrence relation（recursive equations) 的話:

對problem size = n的problem來說，判斷midpoint是否為key所花的時間是一個常數c，如果midpoint不是key，則我們可以拿掉n/2的input，所以剩下的時間就是剩下的n/2 size 的subproblem所需要的worst case running time。

最差都沒找到的話，總共做了 log_2(n) + 1次的midpoint check，以n = 4來說，總共找了n = 4, n = 2, n = 1，總共3次的midpoint check。所以這是theta(log(n))。