Winter is coming! During the contest, your first job is to design a standard heater with a fixed warm radius to warm all the houses.

Every house can be warmed, as long as the house is within the heater's warm radius range.

Given the positions of houses and heaters on a horizontal line, return the minimum radius standard of heaters so that those heaters could cover all houses.

Notice that all the heaters follow your radius standard, and the warm radius will the same.

冬天快來了!在比賽期間，你的第一份工作就是設計一個標準的加熱器，而這加熱器有一個固定的加熱半徑以便能使所有房子都維持溫暖。

只要房子在加熱器的加熱半徑範圍內，每個房子都能被加熱。

給定房子以及加熱器的位置都在同一水平線，請回傳最小的加熱半徑，在這最小的加熱半徑內所有的房子都能被加熱。

請注意所有的加熱器都將遵循你的半徑範圍標準，且每一台加熱器的加熱半徑都相同。

這題有很多種解法，為了呼應前面的patterns主題——Binary Search(二分法搜尋)，這邊就以Binary Search(二分法搜尋)進行解題囉!

先理解題目，以上面Example 2來看，如下圖示意，加熱器會在 1 跟 4 的位置，所以這兩台加熱器的最短加熱半徑必須是1，因為在位置 1 的加熱器的加熱半徑範圍可以涵蓋位置 1、2 的房子;同理，位置 4 的加熱器的加熱半徑範圍可以涵蓋位置 3、4 的房子。

houses = [1,2,3,4], heaters = [1,4]
houses代表符號: ∩
heaters代表符號: ▲
houses + heaters → ∩▲ , ∩ , ∩ , ∩▲

解題思路
從上面範例理解，必須要逐一確認每間房子距離最近的加熱器，並找出最短半徑。

1. 首先，先排序加熱器的位置，確保加熱器的位置排序和房子是同方向
2. for loop跑迴圈，逐一檢查每間房子與加熱器的最短距離
   • 設定加熱器陣列的 起點left 與 終點right
   • 開始使用二分法搜尋(Binary Search)，利用while loop，只要 right 還保持在 left 的右側，就繼續搜尋
     • 先算出目前的中點 mid
       • 若加熱器中點在房子左側，那麼left移到mid的左側(縮小要搜尋的範圍)
       • 若加熱器中點在房子右側，那麼right移到mid的位置(縮小要搜尋的範圍)
     • 取得距離房子最近的加熱器位置後，算出離當前房子最近的兩個加熱器的距離
     • 求得最近距離後，與當前最近距離比較，兩者取較小值
3. 遍歷完所有房子後，回傳最小半徑距離

程式碼

function findRadius(houses, heaters) {
    let res = 0;
    let n = heaters.length;
    heaters.sort((a, b) => a - b); // 排序加熱器的位置

    for (let house of houses) {
        let left = 0, right = n; // 加熱器陣列的起點與終點
        
        // Binary Search
        while (left < right) {
            let mid = Math.floor((left + right) / 2);
            if (heaters[mid] < house) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 計算離當前房子最近的兩個加熱器的距離
        let dist1 = (right === n) ? Number.MAX_SAFE_INTEGER : heaters[right] - house;
        let dist2 = (right === 0) ? Number.MAX_SAFE_INTEGER : house - heaters[right - 1];

        // 選擇離房子最近的加熱器距離，並更新結果
        res = Math.max(res, Math.min(dist1, dist2));
    }

    return res;
}