詳細概念請參考他篇解題報告，這篇專注於優化。

以二元搜找出最小直徑：

n = 5, k = 2,

p = [1, 2, 5, 7, 8]

在上述情況中，我們需要從直徑1~7(p[n - 1] - p[0])中，找出第一個通過測試的直徑(最小直徑)。

我們要用二元搜找出第一個True，但注意二元搜只能用在已排序陣列！

這是一個普通的二元搜寫法不多解釋，它有一個小問題，如果陣列裡有重複的元素，我不能保證拿到的是哪一個。

如果我要從[0, 0, 1, 1, 1, 1, 1]裡面得到最左邊的1該怎麼做，我們需要給它變形一下。

但也可以換個想法，取得第一個比0大的元素(不一定是1)，我偏好用這個，因為晚點還會用到。

接著只要把陣列改成函式就好了(diameter_test是直徑的測試函式)，另外如果k = 1時可以直接輸出最大範圍，到目前為止如果用線性搜的方式完成測試函式，大概可以得到0.6~0.7s的成績。

(測試函式的概念和想法可以去看其他篇解題報告。)

有些人可能會想用二元搜的方式去做，但你會很意外的發現竟然變成了4.Xs。

重點來了，WHY? WHAT HAPPENED? 接下來會講到時間複雜度，不多做解釋。

線性檢查的情況下，不考慮提前結束，總共會檢查k次(基地台數量)，但彼此範圍不重複，時間複雜度最壞為O(n)。

假設基地台的分布非常平均，時間複雜度為O(n * (d * k / l))，d是當前測試的直徑長度(1 <= d <= l // k)，k是基地台數量，l是服務點的最大範圍。

d * k / l恆小於等於1，因此快過O(n)一點。

二元搜的情況下，不考慮提前結束，一樣會檢查k次，但彼此範圍會小幅重複(left可以避免前段的重複，但right恆為n-1)，時間最壞約為O(log2(n) * k)。

假設基地台的分布非常平均，時間複雜度為O(log2(n) * k - 1 / ln(2))，解釋需要一點微積分概念，不懂沒關係。

假設範圍n每次搜尋都會縮小1 / k倍(因為平均分布)，那時間複雜度為Σ(x = 1, k) log2(x / k * n)也就是黎曼和，用積分取近似值log2(n) * k - ∫(0, 1) log2(x) dx = log2(n) - 1 / ln(2)。

看不懂嗎？沒關係總之就是線性搜需要這麼多次n * (d * k / l)，而二元搜要這麼多次log2(n) * k - 1 / ln(2)，我們可以提前計算哪個快，再根據情況選擇策略。

n, k, l在測試中是固定的，變因是d，因此我可以寫出個判別式(需導入math模組)：

d < (math.log2(n) - 1 / math.log(2) / k) * l / n

 

投入實作如下：

不過其實用線性搜就夠了，這篇只是想分享一下比較好的演算法，還有告訴大家微積分很重要，上課別偷懶啊！

 

前幾年系統好像有更新，程式跑得會變慢，因此這應該是目前最好的解法了，有問題歡迎提出！