tioj 1208 第K大連續和

二分搜答案 -> MergeSort求有多少個大於此答案

Merge Sort 那邊不太難，自己想（用雙指標，跟普通的Merge Sort差不多）

重點是二分搜答案的部份！！很容易沒想清楚TLE！！

這裡要來好好分析一下二分搜，不要再亂用猜的方式去寫答案

1. 最基本的：

while( lb < rb ){
        int mid = ( lb + rb ) / 2;
        if( ... ) lb = mid+1;
        else rb = mid;
}

想法：每次都減少範圍，直到 lb == rb。（... 為答案不可能是 mid 的情況）

證明：

當 rb - lb > 1時，rb >= lb+2，故mid >= lb+1（且mid < rb）

若情況為if，則範圍變小。若情況為else，則範圍亦變小。

當 rb - lb == 1 時，若 0 <= lb，則mid = lb，不管如何範圍都變小。

但若 lb < 0，則mid = rb，有可能範圍是不會變小的。（也就會引到TLE）


2. 較複雜的：

while( lb < rb-1 ){
       int mid = ( lb + rb ) / 2;
       if( ... ) lb = mid;
       else rb = mid;
}

 想法：rb 是指向最上界 + 1（... 為答案不可能是 mid 的情況）

證明：

當 rb - lb > 1時，一切都跟最基本的證明相同，無論如何範圍都會變小。

但是 rb 不會等於 lb+1，所以下面會引到TLE的點不存在，故不會引到TLE。


我的code：http://codepad.org/Gxh07Lzj