658. Find K Closest Elements
解題說明
Find K Closest Elements
題目描述：給定一個已升序排序的整數陣列 arr，以及整數 k 和 x。回傳陣列中距離 x 最近的 k 個元素，結果須升序排列。若兩元素距離 x 相等，取值較小者（即較靠左者）。
解題思路（二分搜尋左起點）：
答案是 arr 中一段長度為 k 的連續子陣列 arr[left..left+k-1]。因此問題轉化為：找最優的左起點 left。
左起點的搜尋範圍為 [0, n-k]（確保有 k 個元素可取）。
比較法則：對於候選左起點 mid，比較「窗口左端 arr[mid] 距 x 的距離」與「窗口右端下一個 arr[mid+k] 距 x 的距離」：
- 若
x - arr[mid] > arr[mid+k] - x：左端點離 x 更遠，窗口應右移，故left = mid + 1。 - 否則（
x - arr[mid] <= arr[mid+k] - x）：右端點離 x 更遠或相等，應保留當前或更左的窗口，故right = mid。
等距處理：條件中使用 > 而非 >=，使得等距時偏向取較小值（即保留 arr[mid]），符合題目要求。
終止：left == right 時即為最優左起點，返回 arr[left..left+k-1]。
C++ 解法
複雜度分析
時間複雜度：O(log(n - k) + k) — 二分搜尋在長度 n-k 的範圍內執行，需 O(log(n-k)) 次迭代；建立結果陣列需 O(k)；整體 O(log(n-k) + k)。若 k 相對 n 較小，接近 O(log n)；若需要 O(1) 空間（直接回傳迭代器範圍），則純搜尋部分為 O(log(n-k))。
空間複雜度：O(1)（不計輸出陣列）— 二分搜尋過程僅使用常數額外空間。
虛擬碼
Function findClosestElements(arr, k, x):
n = length of arr
left = 0
right = n - k // valid left endpoints: [0, n-k]
While left < right:
mid = left + (right - left) / 2
// Compare distance of window's left end vs. element just outside right end
If (x - arr[mid]) > (arr[mid + k] - x):
left = mid + 1 // left end too far, shift window right
Else:
right = mid // right end farther (or equal), keep current or go left
// left == right: optimal starting index found
Return arr[left .. left+k-1]其他解法
最大堆 O(n log k)：遍歷陣列，維護大小為 k 的最大堆，按距離 x 的遠近排序（若距離相等按值排序）。每次新元素比堆頂更近時彈出堆頂並插入新元素。最後堆中的 k 個元素即為答案，需排序輸出。時間 O(n log k)，比二分搜尋慢，但不需要陣列已排序。
兩指針（已排序陣列）O(n)：先用二分找到最接近 x 的位置，然後用兩指針分別向左右擴展，每次取距離較近的方向。適合不需考慮等距選左的簡化版本，但處理邊界與等距邏輯較繁瑣。
直接二分 + 窗口 O(log n + k)：先用 lower_bound 找到 x 的插入位置，然後以此為中心雙指針向外擴展取 k 個最近元素。邏輯直觀，但實作時需小心索引越界及等距比較的一致性。
延伸思考
- 若陣列未排序，哪種方法最優？時間複雜度如何比較二分搜尋法（先排序）與最大堆法？
- 本題二分搜尋的「搜尋左起點」技巧可以推廣到哪些類似問題？（例如：找最優窗口起點的通用模板）
- 若 x 不一定是整數（例如 x = 2.5），比較邏輯需要如何調整以正確處理距離相等的情況？