34. Find First and Last Position of Element in Sorted Array

Find First and Last Position of Element in Sorted Array

題目描述：給定一個升序排列的整數陣列 nums 以及目標值 target，找出 target 在陣列中的起始位置和結束位置。若 target 不存在，回傳 [-1, -1]。要求時間複雜度 O(log n)。

解題思路：執行兩次獨立的二分搜尋：

1. 找左邊界（lower bound）：在找到 nums[mid] == target 時不立即回傳，而是記錄當前位置並繼續往左搜尋（hi = mid - 1），最終得到最左側的 target 索引。

2. 找右邊界（upper bound）：在找到 nums[mid] == target 時同樣不立即回傳，記錄當前位置並繼續往右搜尋（lo = mid + 1），最終得到最右側的 target 索引。

若左邊界搜尋後結果為 -1，代表 target 不存在，直接回傳 [-1, -1]。

時間複雜度：O(log n) — 執行兩次各自獨立的二分搜尋，每次 O(log n)，總計仍為 O(log n)。

空間複雜度：O(1) — 只使用常數個變數，不需要額外的資料結構。

方法一：使用 STL lower_bound / upper_bound 利用 std::lower_bound 找到第一個 ≥ target 的位置，再用 std::upper_bound 找到第一個 > target 的位置，兩者之差即為 target 的範圍。程式碼最簡潔，時間複雜度 O(log n)，但需要注意 upper_bound - 1 才是右邊界，且需驗證 lower_bound 指向的值確實等於 target。

方法二：單次二分 + 向外線性擴展 先用普通二分找到任意一個 target，然後向左右兩側線性擴展找邊界。時間複雜度最差為 O(n)（如全部元素都是 target），不符合本題 O(log n) 要求，但實作最直覺。

1. 如果需要計算 target 出現的次數，你會如何利用本題的結果，而不需要額外掃描陣列？
2. 若陣列中的元素是浮點數且可能有精度誤差，如何安全地進行二分搜尋並找到邊界？
3. 這道題可以推廣到找「第一個大於 target 的元素」和「最後一個小於 target 的元素」，請說明如何調整左右邊界的二分邏輯來實現這兩個功能。