## 【LeetCode刷題】【Binary Search 演算法學習筆記】34. Find First and Last Position of Element in Sorted Array
* 學習時間：2025/01/28 (Tue.) ~ 01/30 (Thu.)
* **題目連結（美服）：**[34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/)
* **題目連結（國服）：**[34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/)
* **灵茶山艾府二分搜尋法影片解說：** [二分查找 红蓝染色法](https://www.bilibili.com/video/BV1AP41137w7/?vd_source=e0b39ef55fea35a347aa1da490ac5b01)
### A. 解題技術點
---
1. [陣列（Array）](https://hackmd.io/@oliver-jhih-cs/ryO4s7MdJe)
2. [二分搜尋法（Binary Search）](https://hackmd.io/@oliver-jhih-cs/rJI1aXz_yg)
3. [時間複雜度（Time Complexity）](https://medium.com/appworks-school/初學者學演算法-從時間複雜度認識常見演算法-一-b46fece65ba5)
4. [二分法的區間](https://medium.com/@CecileLiu/二分法的區間-網路上最詳盡的解說-5adf3be3bc5e) ⭐️
### B. 題目
---
> Given an array of integers ==nums== sorted in non-decreasing order, find the starting and ending position of a given ==target== value.
If target is not found in the array, return ==[-1, -1]==.
> You must write an algorithm with **O(log n)** runtime complexity.
### C. 題意（中文）
---
>给你一个按照非递减顺序排列的整数数组 ==nums==，和一个目标值 ==target==。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 ==[-1, -1]==。
>你必须设计并实现时间复杂度为 **O(log n)** 的算法解决此问题。
### D. 參考程式碼
:::spoiler Solution (閉區間)
``` python3
# reference: [灵茶山艾府](https://www.bilibili.com/video/BV1AP41137w7/?vd_source=e0b39ef55fea35a347aa1da490ac5b01)
# 閉區間寫法 [left, right]
# start: >= target
# end: <= target
from typing import List
class Solution:
def lower_bound(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1 # right 為 len(nums) - 1
# 循環終止條件; 區間不為空
# 修改為 while left <= right
while left <= right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1 # 右邊界縮小為 mid - 1
return left # ⭐️left 是第一個 >= target 的索引
def searchRange(self, nums: List[int], target: int) -> List[int]:
start = self.lower_bound(nums, target)
if start == len(nums) or nums[start] != target:
return [-1, -1]
# >= x 即是 left = start
# > x 即是 (>= x) + 1
# < x 即是 (>= x) - 1
# <= x 即是 ( > x) - 1 = end
end = self.lower_bound(nums, target + 1) - 1
return [start, end]
```
:::
:::spoiler Solution (左閉右開區間)
詳見 ➡︎ [灵茶山艾府](https://www.bilibili.com/video/BV1AP41137w7/?vd_source=e0b39ef55fea35a347aa1da490ac5b01)
:::
:::spoiler Solution (開區間)
```python
from typing import List
# 開區間寫法 (left, right）
# left 指向 -1
# Right 指向 n (len(nums))
class Solution:
# lower_bound return 最小滿足 nums[i] >= target的下標 " i "
# 處理特別條件 ☞ 當陣列為空，或者所有數皆小於 target，則返回len(nums)
# 要求 nums 非遞減，即 nums[i] < nums[i+1]
def lower_bound(self, nums: List[int], target: int) -> int:
left, right = -1, len(nums) # 左閉右開區間 [left, right)
# 循環終止條件; 區間不為空
# 右開修改為 while left < right
while left + 1 < right:
mid = left + (right - left) // 2
# 循環不變量
# nums[left] < target
# nums[right] >= target
if nums[mid] < target: # 左邊界縮小為 (mid, right)
left = mid
else:
right = mid # 右邊界縮小為 (left, mid)
# ⭐️循環結束後，left + 1 = right
# 此時，nums[left] < target; nums[right] >= target
# 所以 right 第一個元素 即是 >= target 的元素下標
# start 即是 nums[i] >= target
return right
def searchRange(self, nums: List[int], target: int) -> List[int]:
start = self.lower_bound(nums, target)
if start == len(nums) or nums[start] != target:
return [-1, -1] # nums 中不存在 target
# 如果 start 存在，則 end 必存在
# end: 即是 nums[i] <= target
# <= : 即是比 target 大的最小數，的前一項
# <= : 即是 (nums[i] > target) - 1
end = self.lower_bound(nums, target + 1) - 1
return [start, end]
```
:::
---
:::spoiler Thinking（思路）
有一個遞增排序的數組 nums，我們要找出某個數 target 出現的第一個和最後一個位置。如果 target 不在 nums 裡，就回傳 [-1, -1]。
==解法==
A. 直觀解法 ☞ **線性掃描**
1. 從頭開始找 target 出現的第一個位置
2. 從尾端來找 target 出現的最後一個位置
3. 時間複雜度是 O(n)，不符合 O(log n) 的要求。
B. **二分搜尋法 (Binary Search)**
高效解法—用二分搜尋法找上下界
我們會做 兩次二分搜尋：
* 第一次找左邊界 (first position)
* 第二次找右邊界 (last position)
---
**🔹 找左邊界（First Position）**
* 二分搜尋時，如果 nums[mid] == target，不要馬上返 回，而是繼續往左找。
* 因此如果 nums[mid] == target，我們縮小範圍 right = mid，讓 mid 往左移動。
* 最後當 left == right 時，這個 left 就是 target 最早出現的位置。
**🔹 找右邊界（Last Position）**
* 這次當 nums[mid] == target 時，我們往右邊找，所以 left = mid + 1。
* 最後 right - 1 會是 target 最後出現的位置。
:::
:::spoiler Note（筆記）
1. **Binary Search Basic**
* It works only on sorted (已排序的) arrays.
* The idea (方法) is divide (分割) the search range in half reapetedly (反覆).
2. **Efficiency (效率)**
* Time complexity: **O(log n)** because the ==lower bound== is halved (一半) at each step.
* Space complexity: **O(1)** Since no extra (額外的) space is used.
Sign in with Wallet
Connect another wallet