題目

解題概念

  • 此題簡單來說，就是要從一陣列 nums 中，找出目標值 target 的第一個與最後一個位置
  • 由於題目要求 Runtime Complexity 為 $O(\log n)$，因此搜尋的方式就不能使用線性搜尋，而是要用Binary Search (二元搜尋法)
    • 定義 : 可參考此網頁
    • 此題我將使用 Binary Search 的遞迴寫法
  • 而在實際執行上 :
    1. 先建立一陣列 item
    2. 跑 Binary Search，若有發現目標，就將其索引值加入 item 中
    3. 最後回傳 item 的最小 & 最大值

實際寫Code

  • 目標函式 : searchRange(nums, target)
    • Input : nums: List[int]、target: int
    • Output : List[int]
  • 前置作業 : 
    1
    2
    length = len(nums)
    item = []
  • 主要遞迴 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
     def search(arr, i, j):
        if i > j :
            return

        mid = (i + j) // 2 # 取中間索引值

        # 若找到目標，保存其索引值
        if arr[mid] == target : 
            item.append(mid)

        # 向左搜尋
        search(arr, i, mid-1)

        # 向右搜尋
        search(arr, mid+1, j)
            
    search(nums, 0, length-1)
  • 最後回傳 : 
    1
    2
    3
    4
    5
    6
    7
    8
    if len(item) == 0:
        return [-1, -1] # 沒有找到目標

    elif len(item) == 1:
        return [item[0], item[0]] # 只有找到一個目標

    else:
        return [min(item), max(item)] # 找到兩個以上的目標

參考資料

  1. 二分搜尋法（Binary Search）完整教學（一）