題目出處
難度
easy
題目分類
Array, Binary Search
2026-08-07 二刷
個人範例程式碼 - 二刷 (2026/08/07)
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums)-1
while left <= right: # [1] find 1, idx 0 <= 0
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target: # [1,2] find 2 ok
left = mid + 1
else: # nums[mid] > target:
right = mid - 1
return -1
算法說明
經典的二分搜尋法，需留意最常出錯的兩組測資，
- [1] find 1, 可以看出 idx left <= right 的等號有沒有妥善被處理。
- [1, 2] find 2, 可以看出 left = mid + 1 有沒有能成功找到位於右側的值，而不是停在 mid 沒有繼續搜尋。
Time Complexity
O(logN)
Space Complexity
O(1)
Boundary conditions
- []
- [1] find 0
- [1] find 1 # 可以分析出邊界條件 while left <= right
- [1, 2] find 1
- [1, 2] find 2 # 分析出邊界條件 left = mid + 1 能處理
2022-04-01 一刷
個人範例程式碼 - 一刷 (2022/04/01)
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums:
return -1
start, end = 0, len(nums)-1
while(start + 1 < end):
mid = (start + end) // 2
if nums[mid] == target: # to find first, move end
end = mid
elif nums[mid] < target:
start = mid
else: # nums[mid] > target:
end = mid
else: # when quit loop
if nums[start] == target:
return start
elif nums[end] == target:
return end
else:
return -1
return -1
算法說明
基本的 binary search，採用的策略為先縮小範圍再得到答案。
也就是說 left, right 縮小至最小範圍的 left, right，再去判斷答案。
- 當然比較常見的方法是：left, right 找 mid，mid 直接找到答案會更為簡潔。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
注意 input nums 為 [] 的時候的處理，return 個 -1 給他
Boundary conditions
start 與 end 的處理一直都是 binary search 常出錯的地方，這邊要細心一些。
我採用網路上看到的 start + 1 < end 的方式，先縮小 left, right 範圍
並且不把目標放在直接找到 mid 做為答案。
再從最小範圍 left, right 中找到最終解答。